题目链接:点击进入 上次做了一个类似的,不过是每次只能取一个的.这次规定可以一次取多个了.定义状态dp[i][j]表示面对区间(i,j)时可以得到的最大分数,然后dp[i][j]=max(sum[i+k][j]-dp[i+k][j]+sum[i][i-k+1],sum[i][j-k]-dp[i][j-k]+sum[j-k+1][j]).综合一下就是dp[i][j]=sum[i][j]-min(dp[i+k][j],dp[i][j-k]).其中sum[i][j]表示区间(i,j)之和,1<=k<=j-i+1.这个题目用记忆话搜索实现比较好.
代码如下:
;a[maxn],sum[maxn][maxn];int d[maxn][maxn];int dp(int i,int j){int& ans=d[i][j];if(ans>-1*INF) return ans;if(j<i) return 0;ans=-1*INF;for(int k=1;k<=j-i+1;k++)ans=max(sum[i][j]-min(dp(i+k,j),dp(i,j-k)),ans);return ans;}int main(){int n;freopen(“in.txt”,”r”,stdin);while(scanf(“%d”,&n)&&n){for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=-1*INF;memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)sum[i][j]=sum[i][j-1]+a[j];int ans=dp(1,n);printf(“%d\n”,ans*2-sum[1][n]);} return 0;}
，我只愿，在你的理想和希望里能为你增加一点鼓励，
