【bzoj 2017】硬币游戏

传送门~
非常棒的一道题。 f[i][j] $f[i][j]$表示剩i枚硬币时取j个最多拿到多少， sum[i] $sum[i]$表示最后i枚硬币的价值和，状态转移为：
f[i][j]=sum[i]−max(f[i−j][1]...f[i−j][j∗2]) $f[i][j]=sum[i]-max(f[i-j][1]...f[i-j][j\ast 2])$。
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
int f[2005][2005],num[2005][2005];
int s[2005],sum[2005];
int n;
int main(){
    scanf("%d",&n);
    for(int i=n;i>=1;i--)  scanf("%d",&s[i]);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i];
    for(int i=1;i<=n;i++)  {f[1][i]=s[1];num[1][i]=s[1];}
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j>i) {f[i][j]=f[i][j-1];continue;}
            int o=min(j*2,n);f[i][j]=sum[i]-num[i-j][o];
        }
        num[i][1]=f[i][1];
        for(int j=2;j<=n;j++) num[i][j]=max(num[i][j-1],f[i][j]);
    }
    printf("%d",num[n][2]);
    return 0;
}