题目
https://www.luogu.org/problemnew/show/P2734
思路
状态只有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]。
代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,i,j;
int a[101];
int f[101][101];
int s[101];
int main()
{scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&a[i]);s[i]=s[i-1]+a[i]; f[i][i]=a[i]; }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;
}