题解 | #队伍配置#
队伍配置
https://ac.nowcoder.com/acm/problem/14699
本题从者和装备都只能使用一次，证明是一个01背包问题。但是条件中对于装备又受从者的限制，从者也最多只能有5个。除此之外还有cost值的限制。再加上每一个装备或者从者本身都就有4个东西需要去维护了。而对于装备或者从者本身可以使用滚动数组的方式不需要去创建一个数组维度。
那么本题中装备的维度必须在从者之后，因为能够装多少件装备是由从者去决定的，对于cost值来说放前放后到时都行。
在这里dp[i][j][k]。其中i表示cost值，j表示从者数量，k表示装备数量。总体代表在在这些条件下的最大ATK值。
那么在某个cost下装备的数值其实取决于从者的数值，所以先计算出从者的最大ATK值，然后根据这个花费下的从者的最大ATK值得到装备k件装备的最大ATK值。
最后再遍历一遍求最大值即可。
#include <bits/stdc++.h>
using namespace std;
int n, m, d;
int dp[138+2][300+2][300+2];
int main() {
int x, y;
cin>>n>>m>>d;
for (int k=1;k<=n;k++) {
cin>>x>>y;
for (int i=d;i>=y;i--) {
for (int j=1;j<=5;j++) {
dp[i][j][0] = max(dp[i][j][0], dp[i-y][j-1][0]+x);
}
}
}
while (m--) {
cin>>x>>y;
for (int i=d;i>=y;i--) {
for (int j=1;j<=5;j++) {
for (int k=1;k<=j;k++) {
dp[i][j][k] = max(dp[i][j][k], dp[i-y][j][k-1]+x);
}
}
}
}
int ans=-1;
for( int i=0;i<=d;i++ )
for( int j=0;j<=5;j++ )
for( int k=0;k<=5;k++ ) ans=max(ans,dp[i][j][k]);
printf("%d\n",ans);
return 0;
}
京东开奖150人在聊
