本文共 889 字，大约阅读时间需要 2 分钟。

题目描述

众所周知，湖科大的ACM实验室是大神的聚集地，谁都希望进去一览大神风采。然而，大神一般都是神秘莫测的，不是想见就能见的！这不，ACM实验室的门禁系统就需要正确回答一个问题才会开门。

问题如下：

有一个有限长度的序列 a1,a2,...,an ，你和系统轮流操作（你是先手），每次操作可以取出序列首部或尾部的一个数字，直到序列取尽。设你最终取得的所有数字之和为S，你要让S越大越好。但是系统会让S的最大值尽可能小。

      根据以上规则，你能算出S的最大值吗？

如果你输出的S的最大值是对的，那么恭喜你，你很有机会和大神肩并肩哦^-^。

输入

输入由多组数据组成（不超过100组，其中数据量达到100的不足35组）。

每组数据包括两行：

第一行是一个n，表示序列长度，数据保证1<=n<=1000。

     第二行包含n个数ai，用空格分隔开，数据保证-1000<=ai<=1000，1<=i<=n。

输出

每组输入数据对应一行输出，只包含一个数字，就是S的最大值。

样例输入

5-150 -182 699 -231 1208478 562 437 631 -390 -941 966 -411

样例输出

-2931491

提示

题意：你和系统在一个序列两端轮流取值，你要让所取数字之和S最大，系统会尽可能让S小。

解题思路：n<=1000,所以可以用区间DP来保存在当前区间比对方所取数之和多dp[i][j]。

AC代码：#include
   
    using namespace std;int dp[1005][1005],a[1005],n;int main(){    while(scanf("%d",&n)==1)    {        int sum=0;        for(int i=0;i
   

转载地址：https://blog.csdn.net/qq_44632981/article/details/99694854 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！