2022_ACM_ICPC 杭州站

C.No Bug No Game

思路

1. 与传统背包问题不同的是，在背包剩余质量无法完全装下某个物品时，可以选择添加其部分质量以获得部分价值。易得，最多有一个物品添加的是其部分质量。
2. 记 $sum$ 为 $\sum _{i=1}^n{p}_i$，若 $sum\le k$，则说明不会出现部分质量的情形，即背包容量不会完全或恰恰被装满。此时，答案便是 $\sum _{i=1}^n{w}_{i,pi}$。（没有考虑这种情形，WA 了好几次。）
3. 若 $sum>k$，则说明会出现部分质量的问题，在最后背包一定是被装满的。若不然，则可以添加一个物品的部分质量使其装满。因为最多有一个物品添加的是其部分质量，所以我们可以枚举这个物品 $i$，设定他在背包中的质量为 $m,m\in [1,p_i]$，则对于其他的物品就是背包总质量为 $k-m$ 的传统背包问题，记其答案为 $s_{i,k-m}$。则最后的答案便是 max ⁡ { w i , m + s i , k − m ∣ i ∈ [ 1 , n ] , m ∈ [ 1 , p i ] } max{w_{i,m}+s_{i,k-m}|iin[1,n],min[1,p_i]} max{wi,m​+si,k−m​∣i∈[1,n],m∈[1,pi​]}
4. 考虑如何获得对于其他的物品的背包总质量为 $k-m$ 的传统背包问题的答案。每一次都去计算这个背包显然不优。考虑把 $k-m$ 分为两部分 $l$ 与 $r$，则这个背包问题的答案可以看作前 $i-1$ 个物品装 $l$ 的背包的价值最大值与后 $n-i$ 个物品装 $r$ 的背包的价值最大值的和的最大值。故我们可以预处理两个背包，$d{p}_{i,j,0}$ 表示从 $1$ 开始选，已选到第 $i$ 个物品，目前背包中质量为 $j$ 的最大价值，$d{p}_{i,j,1}$ 表示从第 $n$ 个物体开始选，已选到第 $i$ 个物体，目前背包质量为 $j$ 的最大价值。则 s i , k − m = max ⁡ { d p i − 1 , l , 0 + d p i + 1 , r , 1 ∣ l ∈ [ 0 , k − m ] } s_{i,k-m}=max{dp_{i-1,l,0}+dp_{i+1,r,1}|lin[0,k-m]} si,k−m​=max{dpi−1,l,0​+dpi+1,r,1​∣l∈[0,k−m]}。
5. 考虑两个背包的初始化与转移方程。初始化：$d{p}_{0,0,0}=0,d{p}_{n+1,0,1}=0$。以 $d{p}_{i,j,0}$ 的转移方程为例。首先，我们可以不选第 $i$ 个物品，于是 $\forall j\in [0,k]$，有 $d{p}_{i,j,0}=d{p}_{i-1,j,0}$。其次，如果我们选的话，一定有 $j\ge p_i$，这时有 $d{p}_{i,j,0}=\max (d{p}_{i,j,0},d{p}_{i-1,j-p_i,0}+w_{i,p_i})$。
6. 时间复杂度为 $\mathcal{O}(nkp)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
int dp[maxn][maxn][2], n, k, p[maxn], w[maxn][20];
int sum;
int main ()
{
scanf ("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf ("%d", &p[i]), sum += p[i];
for (int j = 1; j <= p[i]; j++)
scanf ("%d", &w[i][j]);
}
if (sum <= k)
{
int ans = 0;
for (int i = 1; i <= n; i++)
ans += w[i][p[i]];
printf ("%d", ans);
exit (0);
}
memset (dp, -1, sizeof (dp));
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
{
dp[i][j][0] = dp[i - 1][j][0];
if (j >= p[i] && dp[i - 1][j - p[i]][0] != -1)
dp[i][j][0] = max (dp[i][j][0], dp[i - 1][j - p[i]][0] + w[i][p[i]]);
}
dp[n + 1][0][1] = 0;
for (int i = n; i >= 1; i--)
{
for (int j = 0; j <= k; j++)
{
dp[i][j][1] = dp[i + 1][j][1];
if (j >= p[i] && dp[i + 1][j - p[i]][1] != -1)
dp[i][j][1] = max (dp[i][j][1], dp[i + 1][j - p[i]][1] + w[i][p[i]]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= p[i]; j++)
{
int res = k - j;
for (int l = 0; l <= res; l ++)
{
int r = res - l;
if (dp[i - 1][l][0] != -1 && dp[i + 1][r][1] != -1)
ans = max (ans, w[i][j] + dp[i - 1][l][0] + dp[i + 1][r][1]);
}
}
}
printf ("%d", ans);
return 0;
}

收获

1. 对于于传统背包不同的一点，我们可以预先对其进行特殊化处理。
2. 我们可以利用类似于前缀和与后缀和的 $dp$，解决 $s_{i,j}$ 求解问题。

最后

以上就是轻松橘子为你收集整理的2022_ACM_ICPC 杭州站的全部内容，希望文章能够帮你解决2022_ACM_ICPC 杭州站所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。