玩游戏 题解

背包

血量为背包容量，第i关胜利得到积分i为物品i价值，“第i场比赛的第j关”的物品体积为a[j][i]*2+1 (需要注意：若想“拿下这个物品”，消耗血量必须严格大于对方消耗血量的两倍)。

不难发现，样例中的每一列打乱顺序后不会影响最终总得分，所以可从小到大排序。

最后ans取max 遍历t以内的血量。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=107,M=2e4+7;
int k,n,t,ans,a[N][N],w[N][N],dp[N][M];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>k>>n>>t;
	for(int i = 1;i<=k;i++)//第i场（人）
		for(int j = 1;j<=n;j++)//第j关
			cin>>a[j][i];
	for(int i = 1;i<=n;i++){
		sort(a[i]+1,a[i]+1+k);//每一列排序不影响总得分
		for(int j = 1;j<=k;j++)w[i][j]=a[i][j]*2+1;
	}
	for(int i = 1;i<=n;i++)
		for(int j = 0;j<=k;j++)
			for(int z=w[i][j];z<=t;z++)
				dp[i][z]=max(dp[i][z],dp[i-1][z-w[i][j]]+(i*j));
	for(int i = 0;i<=t;i++)ans=max(ans,dp[n][i]);
	cout<<ans<<'\n';
	return 0;
}

这是一道第一眼复杂第二眼简单实则也不难做不出来会觉得自己糖丸了的题。

设 $dp_{i,j}$ 表示现在玩到了第 $i$ 局，有 $j$ 点血量。

我们枚举每一局，然后必须消耗对方的血量乘二加一才有贡献，否则就一点血也别耗。

然后显然要把对手的消耗排序，只要大的能打，小的一定能打。

然后就可以写状态转移了：

$$dp_{i,nw}=\max( {dp_{i,nw},dp_{i-1,nw},dp_{i-1,nw-xl[j]}+i\times j}) $$

这个 $i$ 枚举第几局， $j$ 枚举打到第几个对手，$xl_j$ 表示打倒 $j$ 这个人需要的代价，然后如果打了，前 $j$ 个人都是可以打的，所以是 $i\times j$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,n,t,a[105][105];
int dp[105][20005],xl[105];
signed main(){
	cin>>k>>n>>t;
	for(int i=1;i<=k;++i){
		for(int j=1;j<=n;++j){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=k;++j)xl[j]=a[j][i]*2+1;
		sort(xl+1,xl+1+k);
		for(int j=1;j<=k;++j){
			for(int nw=0;nw<=t;++nw){
				dp[i][nw]=max(dp[i][nw],dp[i-1][nw]);
				if(nw-xl[j]>=0)dp[i][nw]=max(dp[i][nw],dp[i-1][nw-xl[j]]+i*j);
			}
		}
	}
	int ans=0;
	for (int i=0;i<=t;i++){
		ans=max(ans,dp[n][i]);
	}
	cout<<ans<<"\n";
	return 0;
}