题解
首先,玩家一先选,那么玩家一该选最左边还是最右边呢?
我们假设玩家一有穿越时空的能力,知晓了选择左边后的最大得分和选了右边后的最大得分,那么玩家一便能确定选哪个
设 \(dp[l][r]\) 为当区间为 \(l,r\) 时先手最大分数
选左边的最大得分: \(sumr-dp[2][r]+a[1]\)
选右边的最大得分:\(suml-dp[1][r-1]+a[r]\)
code
#include<bits/stdc++.h>
using namespace std;
int a[205];
int pre[205]={0};
int dp[205][205]={0};
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
for(int l=1;l+i-1<=n;l++)
{
int r=l+i-1;
int suml=pre[r-1]-pre[l-1],sumr=pre[r]-pre[l];
dp[l][r]=max(a[l]+sumr-dp[l+1][r],a[r]+suml-dp[l][r-1]);
}
}
cout<<dp[1][n]<<" "<<pre[n]-dp[1][n];
return 0;
}
标签:pre,得分,205,int,玩家,P2734,Game,USACO3.3,dp
From: https://www.cnblogs.com/pure4knowledge/p/18238805