自动搬运

查看原文

来自洛谷，原作者为

	「QQ红包」 **

搬运于2025-08-24 21:40:58，当前版本为作者最后更新于2016-08-12 11:04:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解by：redbag

经典的区间型动态规划的题。

状态只有2种：从左边拿和从右边拿。

假设当前状态a1,a2,a3,a4,a5，如果第一个人选最左边的，则问题转化为四个数a2,a3,a4,a5，然后第二个人先选，由于题目说第二个人方案也最优，所以选的也是最优方案，即f[i+1][j]；先选右边同理。

f[i][j]表示i~j区间段第一个人选的最优方案。

所以dp转移方程为：f[i][j]=max{ sum[i+1][j]-f[i+1][j]+ai，sum[i][j-1]-f[i][j-1]+aj }

sum[i][j]其实就等于sum[1][j]-sum[1][i-1],于是我们用一个s数组，s[i]表示前1~i个数的和，就好了。

所以dp转移方程也可写成f[i][j]=max((s[j]-s[i-1])-f[i+1][j],(s[j]-s[i-1])-f[i][j-1]);

根据dp转移方程我们可以发现，要得到状态f[i][j],必须要得到状态f[i+1][j]和f[i][j-1]。然后我们就可以写出程序了。

还是很快的。

USER: lanxuan yi [ylx14271]
TASK: game1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4220 KB]
   Test 2: TEST OK [0.000 secs, 4220 KB]
   Test 3: TEST OK [0.000 secs, 4220 KB]
   Test 4: TEST OK [0.000 secs, 4220 KB]
   Test 5: TEST OK [0.000 secs, 4220 KB]
   Test 6: TEST OK [0.000 secs, 4220 KB]
   Test 7: TEST OK [0.000 secs, 4220 KB]
   Test 8: TEST OK [0.000 secs, 4220 KB]
   Test 9: TEST OK [0.000 secs, 4220 KB]
   Test 10: TEST OK [0.000 secs, 4220 KB]
   Test 11: TEST OK [0.000 secs, 4220 KB]
   Test 12: TEST OK [0.000 secs, 4220 KB]
   Test 13: TEST OK [0.000 secs, 4220 KB]
   Test 14: TEST OK [0.000 secs, 4220 KB]
   Test 15: TEST OK [0.000 secs, 4220 KB]
   Test 16: TEST OK [0.000 secs, 4220 KB]

All tests OK.

/*
ID: ylx14271
PROG: game1
LANG: C++     
*/
#include<set>  
#include<map>  
#include<list>  
#include<queue>  
#include<stack>  
#include<string>  
#include<math.h>  
#include<time.h>  
#include<vector>  
#include<bitset>  
#include<memory>  
#include<utility>  
#include<stdio.h>  
#include<sstream>  
#include<iostream>  
#include<stdlib.h>  
#include<string.h>  
#include<algorithm> 
#define LL unsigned long long   
using namespace std;
int n,i,j; 
int a[101];//存数
int f[101][101];
//f[i][j]表示取i~j这个区间段player1最高得分 
int s[101];//s[i]表示a[1]~a[i]的和  
int main() 
{
    freopen("game1.in","r",stdin);
    freopen("game1.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//读入 s
        s[i]=s[i-1]+a[i];//求和 
        f[i][i]=a[i];//初始化 
    }
    //表示a[i]~a[j]的和的方法：s[j]-s[i-1]
    for (i=n-1;i>=1;i--)
        for (j=i+1;j<=n;j++)
            f[i][j]=max((s[j]-s[i-1])-f[i+1][j],
            (s[j]-s[i-1])-f[i][j-1]);
    printf("%d %d\n",f[1][n],s[n]-f[1][n]);
    return 0;
}