P1075 （C++代码）

解题思路:





注意事项:





参考代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,a[2005],f[2005][2005],sum[2005];
int main(){
//    freopen("01.txt","r",stdin);
    scanf("%d",&N);
    for(int i=N;i>0;i--)
        scanf("%d",&a[i]);
    for(int i=1;i<=N;i++)
        sum[i]=sum[i-1]+a[i];
    
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            f[i][j]=f[i][j-1];//自己特有的两条路保留，直接连到f(i,j-1)的最优解上
            if(i-(j<<1)>=0) 
                f[i][j]=max(f[i][j],sum[i]-f[i-(j<<1)][j<<1]);
            if(i-((j<<1)-1)>=0)
                f[i][j]=max(f[i][j],sum[i]-f[i-((j<<1)-1)][(j<<1)-1]);
        }
    printf("%d\n",f[N][1]);
    return 0;
}