题解 P2734 【游戏 A Game】
题解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;
}