bzoj1783: [Usaco2010 Jan]Taking Turns

闲着无事跟zory做题。。。（还星星是权限）

逆推。没了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

LL a[710000];
LL f[710000],nt[710000];//nt表示对手的最优解 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    
    f[n]=a[n];nt[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        if(f[i+1]>nt[i+1]+a[i])
        {
            f[i]=f[i+1];
            nt[i]=nt[i+1];
        }
        else
        {
            f[i]=nt[i+1]+a[i];
            nt[i]=f[i+1];
        }
    }
    printf("%lld %lld
",f[1],nt[1]);
    return 0; 
}