玩游戏 题解

背包

血量为背包容量，第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;
}

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