Usaco2010 Dec Treasure Chest

n個の硬貨は左から右へ、i番目の価値はCiで、AとBは交代で硬貨を取りますが、毎回両側から硬貨を取るしかありません.Aは先に取り始めて、二人とも最善の策略を取って、Aに最大いくらのコインを手に入れることができますか?(n<=5000)
問題解:ゲームdp
f[i][j]が区間[i,j]から得られる最大の価値を表すとすると、f[i][j]=max(a[i]+sum[i+1][j]-f[i+1][j],a[j]+sum[i][j-1]-f[i][j-1])
次のように理解されます.
[i,j]区間については、Aはiを選択するかjを選択し、iを選択すると残りの区間[i+1,j]はBを選択しなければならないので、Bも最適選択であることに注意し、Aは残りの区間[i+1,j]で選択された総和がsum[i+1][j]-f[i+1][j]である(すなわち、Bを減算するのが最も好ましい).
A jを選択した場合、分析は上と同じです.
しかし、この問題のメモリには制限があり、次元を下げる必要があります.
sum[i][j]を接頭辞和に置き換えると、f[i][j]は長さで押すdpに変換する必要があり、f[len][i]はiから長さlenの区間を表す.
f[len][i]=maxc[i]+s[i+len-1]-s[i]-f[len-1][i+1],c[i+len-1]+s[i+len-2]-s[i-1]-f[len-1][i])
そしてlen次元は下がることができます.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[6001],s[6001],c[6001];
int main()
{
    int n;
    while(cin>>n)
    {
        memset(s,0,sizeof(s));
        memset(c,0,sizeof(c));
        memset(f,0,sizeof(f));

        for(int i=1;i<=n;i++)
        {
            cin>>c[i];
            s[i]=s[i-1]+c[i];
            f[i]=c[i];
        }

        for(int len=2;len<=n;len++)
         for(int i=1;i<=n-len+1;i++)
         f[i]=max(c[i]+s[i+len-1]-s[i]-f[i+1],c[i+len-1]+s[i+len-2]-s[i-1]-f[i]);

        cout<<f[1]<<"
";
    }
    return 0;
}