题意： 一排数，两个人轮流取数，保证取的位置递增，每个人要使自己取的数的和尽量大，求两个人都在最优策略下取的和各是多少。
注：双方都知道对方也是按照最优策略取的。。。
傻逼推了半天dp。。。。。。然后看kpm的代码里一个语句解决
KPM大概思路：倒着取，设当前两人最大和分别为A和B（A为先取的人）。。如果B+W[i]>A就把A和B交换（先取的人可以按照更优的取法，后手无人权。。）..让A取W[i]
接下来是蒟蒻的傻逼写法：
f[0][i],f[1][i]分别表示第1个人和第2个人，在i~n中取了第i个数的最大总和。也是倒着取。。。
f[0][i]=max{f[0][j1]}+W[i]，（j1>i）所以我们维护一下j1就好了。但同时，因为有另一个人在取数，所以j1不可能随便取。。。
因为取的位置递增,且对方也是按最优策略取的，所以i<j1<k1；（i<k1<=n且使得f[1][k1]在f[1][i+1…..n]中最大）。
每次算f[0][i]的时候先更新一下k1和j1。。。求f[1][i]的时候同理。
因为k1和j1是递减的，所以总的时间复杂度还是O(n)。
每次碰到有关博弈的题就抓瞎。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
ll f[][maxn],ans,ans1;
int j1,k0,j0,k1,lastj1,lastk1;
int val[maxn];
int i,j,k,n,m;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
int main(){
n=read();
for(i=;i<=n;i++)val[i]=read();j0=k0=n;j1=k1=n+;lastj1=lastk1=n;
f[][n]=f[][n]=val[n];ans=n;
for(i=n-;i;i--){
if(f[][i+]>=f[][j0]){
j0=i+;
for(j=lastj1;j>j0;j--)if(f[][j]>=f[][j1])j1=j;lastj1=j0+;
}
f[][i]=(ll)val[i]+f[][j1];
if(f[][i+]>=f[][k0]){
k0=i+;
for(j=lastk1;j>k0;j--)if(f[][j]>=f[][k1])k1=j;lastk1=k0+;
}
f[][i]=(ll)val[i]+f[][k1];
if(f[][i]>=f[][ans])ans=i;
}
for(i=ans+;i<=n;i++)if(f[][i]>ans1)ans1=f[][i];
printf("%lld %lld\n",f[][ans],ans1);
}
