题目

思路

考虑模拟博弈过程。

题目可以看成:先手希望X - Y最大，后手希望X - Y最小。

显然游戏过程中剩下的数必然是连续的一段。设 dp[i,j]​ 表示剩下下标为 [i,j] 的数时，先手（并非当前的先手而是开始时的先手，下同）能取得的最大分数差。

分两种情况讨论：

                                                                                           从队首取         从队尾取

• 已经取走的数为偶数个，此时先手取，dp[i,j] = max⁡(dp[i + 1,j] + a[i],dp[i,j − 1] + a[j])

• 已经取走的数为奇数个，此时后手取，dp[i,j] = min⁡(dp[i + 1,j] − a[i],dp[i,j − 1] − a[j])

•                                                                                   从队首取         从队尾取

dp 流程与普通的区间 dp 类似，只是少了枚举区间断点的操作。时间复杂度 O(n^2)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10001],dp[5001][5001],sum[5001];
signed main()
{
  cin>>n;
  for(int i = 1;i <= n;i++) cin>>a[i];
  for(int l = 1;l <= n;l++)
    for(int i = 1;i <= n - l + 1;i++)
    {
      int j = i + l - 1;
      if((n - l) % 2 == 0) dp[i][j] = max(dp[i + 1][j] + a[i],dp[i][j - 1] + a[j]);
      else dp[i][j] = min(dp[i + 1][j] - a[i],dp[i][j - 1] - a[j]);
    }
  cout<<dp[1][n];
  return 0;
}

看懂了吗?如果看懂了就请收藏点赞加关注支持一下作者吧!QwQ