题目
题目描述
萌学姐在玩大型手游《futa go》,他现在准备进入作战环节,所以他准备安排自己的队伍。
队伍配置里,可供玩家选择的作战人物被称作“从者”,玩家可以对每个“从者”可以装备至多1件的“概念礼装”,玩家具有一个cost上限值。详细定义如下:
1、 每个从者和概念礼装都具有攻击值ATK。
2、 每个从者和概念礼装都会占据一定的cost值。
3、 每个从者和概念礼装只能上场一次,不能重复使用。
4、 概念礼装只能装备在从者上,不能单独存在。
5、 选择的从者和概念礼装的cost值之和不能超过玩家的cost上限值。
6、 最多可以选择5名从者(在cost值限制下)。
现在给出玩家仓库的每个从者和每件概念礼装的ATK值和cost值,问在满足定义的条件下,队伍可以凑出的最大ATK值。
输入描述
第1行输入三个整数n,m,d,代表玩家仓库的从者数量、概念礼装数量和cost上限值。
第2-n+1行,每行输入两个整数a1,b1,表示第i个从者的ATK值和cost值。
第n+2-n+m+1行,每行输入两个整数a2,b2,表示第i个概念礼装的ATK值和cost值。
数据保证:0<n,m≤300,25≤d≤138,1000≤a1≤15488,500≤a2≤2500,3≤b1,b2≤12
输出描述
输出一行,一个整数,代表可以凑出的最大ATK值。
示例1
输入
4 2 25
2001 5
2002 5
2003 5
4010 10
2004 10
2005 10
输出
10016
说明
派上前4名从者,最大ATK值=2001+2002+2003+4010=10016(cost总值为25=玩家cost上限)
题解
知识点:背包dp。
一眼看上去像分组背包,但其实不是,因为从者、礼装没有明确分组。接下来,定义 \(a[i]\) 和 \(ac[i]\) 为从者的攻击力和花费,\(b[i]\) 和 \(bc[i]\) 为礼装的攻击力和花费。
设 \(dp[i][j][k]\) 为选了 \(i\) 个从者,\(j\) 个礼装,花费为 \(k\) 的最大攻击力。注意是选了,不是考虑到,因此每次考虑要更新所有。先处理选从者的,但没选礼装的所有情况,因为从者没有选的限制,但选礼装必须是选了从者的情况下有。有转移方程:
\[dp[k][0][j] = \max(dp[k][0][j],dp[k-1][0][j-ac[i]] + a[i]) \]表示选 \(k\) 个的状态可以从选 \(k-1\) 的状态转移也可以不选,\(k\) 是 \([1,5]\) 都要跑一遍,因为最多选 \(5\) 个。
随后开始选礼装,有转移方程:
\[dp[k][u][j] = \max (dp[k][u][j],dp[k][u-1][j-bc[i]] +b[i]) \]表示在选 \(k\) 个从者的情况下选 \(u\) 个礼装可以从选 \(k\) 个从者的情况下选 \(u-1\) 个礼装转移也可以不选,\(u\leq k\) 表示不能超过从者数量。
更新时,费用 \(j\) 这维要倒序,因为实际上这个状态已经滚动了考虑到某个礼装/从者一维,所以实际上是考虑到一维、选从者一维、选礼装一维、费用一维的高维背包dp,类似的有二维费用背包。
初始化负无穷,\(dp[0][0][0] = 0\) ,因为选择有严格数量限制,不能选空气。随后答案在 \(dp[i][j][k]\) 的所有状态里面的最大值。
时间复杂度 \(O(nd)\)
空间复杂度 \(O(d)\)
代码
#include <bits/stdc++.h>
using namespace std;
int a[307], ac[307], b[307], bc[307], dp[10][10][150];///表示选了i个从者,j个礼装,费用为k
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, d;
cin >> n >> m >> d;
for (int i = 1;i <= n;i++) cin >> a[i] >> ac[i];
for (int i = 1;i <= m;i++) cin >> b[i] >> bc[i];
memset(dp, -0x3f, sizeof(dp));///选从者的答案要严格保留
dp[0][0][0] = 0;
for (int i = 1;i <= n;i++)///考虑了第i个从者
for (int j = d;j >= ac[i];j--)///费用为j
for (int k = 1;k <= 5;k++)///选k个,一定放在费用下面,否则会重复选同一个
dp[k][0][j] = max(dp[k][0][j], dp[k - 1][0][j - ac[i]] + a[i]);///取费用为j,选k个的最优解
///因为礼装的选择只取决于从者的人数和对应费用和atk无关,因此对于两个状态相同的组合选最优的对礼装选择无影响
for (int i = 1;i <= m;i++)
for (int j = d;j >= bc[i];j--)
for (int k = 1;k <= 5;k++)
for (int u = 1;u <= k;u++)
dp[k][u][j] = max(dp[k][u][j], dp[k][u - 1][j - bc[i]] + b[i]);
int ans = 0;
for (int i = 0;i <= 5;i++)
for (int j = 0;j <= 5;j++)///可能一个礼装都选不了
for (int k = 0;k <= d;k++)
ans = max(ans, dp[i][j][k]);
cout << ans << '\n';
return 0;
}
标签:cost,int,配置,从者,ATK,队伍,礼装,NC14699,dp
From: https://www.cnblogs.com/BlankYang/p/16584444.html