题目链接：点此跳转
题目描述：
萌学姐在玩大型手游《futa go》，他现在准备进入作战环节，所以他准备安排自己的队伍。 队伍配置里，可供玩家选择的作战人物被称作“从者”，玩家可以对每个“从者”可以装备至多1件的“概念礼装”，玩家具有一个cost上限值。详细定义如下：
1、 每个从者和概念礼装都具有攻击值ATK。 2、 每个从者和概念礼装都会占据一定的cost值。 3、 每个从者和概念礼装只能上场一次，不能重复使用。 4、 概念礼装只能装备在从者上，不能单独存在。 5、 选择的从者和概念礼装的cost值之和不能超过玩家的cost上限值。 6、 最多可以选择5名从者（在cost值限制下）。
现在给出玩家仓库的每个从者和每件概念礼装的ATK值和cost值，问在满足定义的条件下，队伍可以凑出的最大ATK值。
解题思路：
题目读完很容易想到这是一个01背包的变形题，难点在于从者和概念礼装的依赖性问题，我们可以开一个三维数组，多出的一维用来记录概念礼装的个数即 dp[i][j][k] ， 要注意满足 k<=j 。我们可以先处理没有概念礼装的情况即k=0，然后递推出有概念礼装的情况。
Code:
#include<iostream> #include<cstring> using namespace std; int dp[607][10][10]; int main(){ int n,m,d; scanf("%d%d%d",&n,&m,&d); int x,y,ans=0; //ans记录答案 for(int i=1;i<=n;i++){ //处理没有概念礼装的情况 scanf("%d%d",&x,&y); for(int j=d;j>=y;j--){ for(int k=1;k<=5;k++){ dp[j][k][0]=max(dp[j][k][0],dp[j-y][k-1][0]+x); ans=max(ans,dp[j][k][0]); } } } for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); for(int j=d;j>=y;j--){ for(int k=1;k<=5;k++){ for(int l=1;l<=k;l++){ // l<=k dp[j][k][l]=max(dp[j][k][l],dp[j-y][k][l-1]+x); ans=max(ans,dp[j][k][l]); } } } } printf("%d\n",ans); return 0; }