bzoj1783 [Usaco2010 Jan]Taking Turns

Turns"/>

bzoj1783 [Usaco2010 Jan]Taking Turns

一开始以为是博弈论（虽然确实是博弈。。）但是后来发现要用dp。。
顺着dp炸了。。
只好倒过来dp。。（按照性质就应该从后往前好吗。。）
从第i个位置开始，第一个为f[1][i],第二个为f[2][i]。
然后我们倒推，，f[1][i]肯定是取当前的a[i]或者i+1-n中最大的那个，取一个max，然后f[2][i]取另外一个就好啦。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m;
ll f[3][N],a[N];
int main()
{scanf("%d",&n);fo(i,1,n)scanf("%d",&a[i]);int pos=n;ll mx=0;fd(i,n,1){f[1][i]=mx;f[2][i]=f[2][pos];if (f[1][i]<=f[2][pos]+a[i]){f[1][i]=f[2][pos]+a[i];mx=f[1][i];pos=i;f[2][i]=f[1][i+1];}}printf("%lld %lld\n",f[1][1],f[2][1]);return 0;
}