水题。。直接暴力DP。。。
dp(pos,last)表示当前在pos。。上一次拿了last。最多能拿多少钱。。
Code。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=2010,maxlast=1010;
int dp[maxn][maxlast]={0};
int C[maxn],n;
void init()
{
cin>>n;
REP(i,n) REP(j,n/2+1)
dp[i][j]=-1;
for(int i=0;i<n;i++)
{
cin>>C[i];
C[i]+=i?C[i-1]:0;
}
}
int DP(int i,int last)
{
int rest=C[n-1]-C[i-1];
last<<=1;
if(n-i-1<=last)
return rest;
if(dp[i][last]!=-1)
return dp[i][last];
int get,ans=0;
for(int take=1;take<=last;take++)
{
get=rest-DP(i+take,take)+C[i+take]-C[i-1];
ans=max(ans,get);
}
return dp[i][last]=ans;
}
int main()
{
init();
cout<<DP(0,1)<<endl;
}