动态规划、博弈论、区间动态规划、记忆化搜索、对抗搜索

题目链接

对抗搜索，从未来向现在递推。令给定序列为 $a$，设计 $dp_{l,r}$ 为两人按照各自的最优策略取完区间 $[l,r]$ 后 $X-Y$ 的值。先手操作时状态转移方程为 $dp_{l,r}=\max(dp_{l+1,r}+a_l,dp_{l,r-1}+a_r)$，后手操作时状态转移方程为 $dp_{l,r}=\min(dp_{l+1,r}-a_l,dp_{l,r-1}-a_r)$，答案为 $dp_{1,n}$，时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1000000000000ll;
long long ans,dp[3005][3005];
int n,a[3005];
void dfs(int l,int r,int x){
    if(~dp[l][r]) return;
    if(l==r) return dp[l][l]=x*a[l],void();
    dfs(l+1,r,-x),dfs(l,r-1,-x);
    if(x==1) dp[l][r]=max(dp[l+1][r]+a[l],dp[l][r-1]+a[r]);
    else dp[l][r]=min(dp[l+1][r]-a[l],dp[l][r-1]-a[r]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    dfs(1,n,1);
    printf("%lld\n",dp[1][n]);
    return 0;
}