AcWing 1388. 游戏(区间dp+零和博弈好题)
原题链接
中等
作者:
逸误
,
2024-04-02 22:22:17
,
所有人可见
,
阅读 61
//博弈论(零和博弈)+区间dp
//状态表示:f[i][j]:i~j区间内,先选者最好情况比后选者高几分
//状态更新:f[i][j]=max(a[i]-f[i+1][j],a[j]-f[i][j-1])
//为什么是减去?因为选完这步后,对面也一定会选择最优策略,这里就是看:对面一定使用最优策略时,选左好还是选右好
#include <iostream>
using namespace std;
const int N = 205;
int n;
int a[N];
int f[N][N];
int sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i][i]=a[i];//只剩这一个选择,那就多a[i]分
sum+=a[i];
}
//区间dp一定要从小区间到大区间,保证依赖条件都更新过!
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
f[l][r]=max(a[l]-f[l+1][r],a[r]-f[l][r-1]);
}
//零和,求出了两人得分之差f[1][n],分数总和不变,就能求每个人得分
cout<<(f[1][n]+sum)/2<<' '<<(sum-f[1][n])/2<<endl;
return 0;
}