目录
A.小红组比赛
B.小红升装备
A.小红组比赛
思路 ：经典的多重背包问题，这里将dp[ i ][ j ]定义为前 i 场比赛的难度 j 是否可能，所以dp只需用0 1 表示，然后遍历dp[ n ][ j ]即可。
代码：
void solve()
{ cin>>n>>m;for(i,1,n)for(j,1,m)cin>>a[i][j];dp[0][0]=1;for(i,1,n)for(j,1,m)for(k,a[i][j],5000)dp[i][k]|=dp[i-1][k-a[i][j]];//注意这里是用或运算，因为dp[i][j]这个难度可能在前1~j-1道题中存在过cin>>tag;int ans=1e9;for(i,0,5000)if(dp[n][i]) ans=min(ans,abs(tag-i));cout<<ans;}
B.小红升装备
思路：本质上是一个固定体积背包，有限制个数选取的最大价值问题，降维DP记得从大到小更新，dp[i]表示花费i个金币能达到的最大战力。
代码：
void solve()
{int n,x;cin>>n>>x;for(int i=1;i<=n;i++){cin>>att[i]>>price[i]>>cost[i]>>up[i]>>lv[i];for(int j=x;j>=0;j--){for(int k=0;k<=lv[i]&&k*cost[i]+price[i]<=j;k++)dp[j]=max(dp[j],dp[j-k*cost[i]-price[i]]+k*up[i]+att[i]);}}cout<<dp[x];
}
