[bzoj1783] [Usaco2010 Jan]Taking Turns

题意： 一排数，两个人轮流取数，保证取的位置递增，每个人要使自己取的数的和尽量大，求两个人都在最优策略下取的和各是多少。

注：双方都知道对方也是按照最优策略取的。。。

傻逼推了半天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);

 }