[게임 DP] BZOJ1783: [Usaco 2010 Jan] Taking Turns

이 바둑은 비교적 간단하다. 모든 사람의 목표는 단지 자신의 점수를 많이 얻는 것일 뿐이다.그래서 직접DP구:fi를 설정하면 0은 i부터 추출하고 먼저 가장 좋은 값을 나타낸다.fi,1은 백핸드의 최우수치입니다.분명히 f,0=max {aj+fj+1,1},fi,1=fpos,0이 있습니다.pos는fi,0이 어디서 옮겨왔는지 나타낸다.

#include
#include
using namespace std;
const int maxn=700015;
typedef long long LL;
int n,a[maxn];
LL f[maxn][2];
int main(){
    freopen("bzoj1783.in","r",stdin);
    freopen("bzoj1783.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int pos=n+1; 
    for(int i=n;i>=1;i--){
        if(a[i]+f[i+1][1]>=a[pos]+f[pos+1][1]) pos=i;
        f[i][0]=a[pos]+f[pos+1][1];
        f[i][1]=f[pos+1][0];
    }
    printf("%lld %lld
",f[1][0],f[1][1]);
    return 0;
}