一开始我们想到 dp[i][j][k] 为到了第 i 轮，a选了 j 个英雄，b选了 k 个英雄的情况。
如果 i%2==1,此时为 a 的pb，所以会让答案尽量的大
如果 i%2==0,此时为 b 的pb，所以会让答案尽量的小
如果现在为 a 的pb，posa= i/2 -k + j+1 为a要不要选的位置
posb=i/2 - j + k+1 为a要不要ban的位置
if( posa<= n && j !=m ) 此时意味着a可以选posa位置的英雄:
无论何种情况下 a 都可以ban了posb位置的英雄
if(round%2==1) { ans=-INF; if(posa<=n&&numa!=m) ans=max(ans,dfs(round+1,numa+1,numb)+a[posa]); ans=max(ans,dfs(round+1,numa,numb)); return dp[round][numa][numb]=ans; }
那么对于b来说，同理，只不过b是希望 dp 越来越小的
posa=i/2-k+j+1 为b要不要ban的位置
posb=i/2-j+k+1 为b要不要选的位置
else { ans=INF; if(posb<=n&&numb!=m) ans=min(ans,dfs(round+1,numa,numb+1)-b[posb]); ans=min(ans,dfs(round+1,numa,numb)); return dp[round][numa][numb]=ans; }
最后由于a,b选手都足够聪明，所以我们让a数组和b数组从大到小排序
初始化：a的轮次要赋值为无穷小，b的轮次要赋值为无穷大，记忆化搜索一般把dp全部memset为-1，但在本题中dp值为-1的情况是存在符合的，所以不能设为-1
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount const int N=1e5+10; //const int M=; //const int inf=1e9; const ll INF=1e18; int T,n,m; ll a[N],b[N],dp[N<<1][12][12]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } ll dfs(int round,int numa,int numb) { if(round>2*n) return 0; if(dp[round][numa][numb]!=INF&&dp[round][numa][numb]!=-INF) return dp[round][numa][numb]; int posa=round/2-numb+numa+1; int posb=round/2-numa+numb+1; ll ans; if(round%2==1) { ans=-INF; if(posa<=n&&numa!=m) ans=max(ans,dfs(round+1,numa+1,numb)+a[posa]); ans=max(ans,dfs(round+1,numa,numb)); return dp[round][numa][numb]=ans; } else { ans=INF; if(posb<=n&&numb!=m) ans=min(ans,dfs(round+1,numa,numb+1)-b[posb]); ans=min(ans,dfs(round+1,numa,numb)); return dp[round][numa][numb]=ans; } } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); n=read(),m=read(); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); sort(a+1,a+n+1,greater<ll>()); sort(b+1,b+n+1,greater<ll>()); for(int i=1;i<=2*n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=m;k++) { if(i%2) dp[i][j][k]=INF; else dp[i][j][k]=-INF; } printf("%lld",dfs(1,0,0)); return 0; }