|
|
题意：有两支队伍，各有由n个英雄组成的英雄池，价值分别为a1,a2....an,和b1,b2.....bn，双方最多可以选取k名英雄，双方队伍轮流操作，每次操作可以从己方英雄英雄池选一位英雄，或者从对面英雄池禁用一位对面没选择的英雄，队伍A最终获得的价值为Sa，队伍B最后获得的价值为Sb，A队伍想让Sa-Sb尽可能大，而B队伍想让Sa-Sb尽可能小，求最终结果。
思路：假设当前选择禁用英雄，一定是禁用对面当前价值最大的英雄，而选择英雄，则是选择当前己方价值最大的英雄，我们需要明确知道当前还剩下的价值最大的英雄是哪一个，而“还剩下”是指自己没有选并且对面没有禁用，如果我们知道双方选取了多少英雄，并且双方禁用了多少英雄，那么我们就知道了当前回合数，反之，我们知道了选了多少英雄，并且当前的回合数，就知道了当前禁用了多少英雄，就可以知道当前回合该选哪个英雄或者该禁用对面哪个英雄。k<=10暗示了我们需要将双方选取的英雄数量作为状态。当该队选取英雄数到达k时，后来只会禁英雄。
当前已经被禁用或者被选择的英雄的总数量为“对面已经操作总数”-“对面选的英雄数”+“自己选的英雄数”
nowa=roundb-numb+numa
nowb=rounda-numa+numb
考虑记忆化搜索 用数组dp[rounda][roundb][numa][numb]，四个状态分别为a的操作数，b的操作数，a选择的英雄数，b选择的英雄数。
实际上也可以用数组dp[round][numa][numb]，三个状态分别为双方操作数的总和，a选择的英雄数，b选择的英雄数。因为操作是轮流进行的，所以自然知道rounda和roundb。
dp数组记录的是Sa-Sb，当A行动时，他要让dp数组尽量大，当B行动时，他要让dp数组尽量小。
代码实现：
#include<bits/stdc++.h>
#define ll long long
const ll inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn=1e5+10;
int a[maxn],b[maxn];
int n,k;
ll dp[maxn*2][11][11];
ll dfs(int round,int numa,int numb)
{
if(round==2*n)
return 0;
if(dp[round][numa][numb]!=-1)
return dp[round][numa][numb];
int nowa=round/2-numb+numa;//a已经被ban或被pick的数量
int nowb=(round+1)/2-numa+numb;//b已经被ban或被pick的数量
if(round%2==0)//现在a行动
{
ll ans=-inf;
if(numa!=k&&nowa!=n)//已经选满k个英雄或无英雄可选
ans=max(ans,dfs(round+1,numa+1,numb)+a[nowa+1]);
ans=max(ans,dfs(round+1,numa,numb));
return dp[round][numa][numb]=ans;
}
else//b行动
{
ll ans=inf;
if(numb!=k&&nowb!=n)//已经选满k个英雄或无英雄可选
ans=min(ans,dfs(round+1,numa,numb+1)-b[nowb+1]);
ans=min(ans,dfs(round+1,numa,numb));
return dp[round][numa][numb]=ans;
}
}
int main()
{
memset(dp,-1,sizeof dp);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a;
for(int i=1;i<=n;i++)
cin>>b;
sort(a+1,a+1+n,greater<int>());
sort(b+1,b+1+n,greater<int>());
cout<<dfs(0,0,0)<<&#39;\n&#39;;
return 0;
} |
|
发表于 2022-12-21 17:26:50