一道不错的 dp 题,下令原背包容量为 \(m\)。
注意到 \(w_i=a\times 2^b\) 中 \(a,b\) 都比较小,尝试按照 \(a\) 或者 \(b\) 分组然后合并,但是显然如果我们按照 \(a\) 分组就会有个问题,那就是背包容量过大无法处理。
于是考虑按照 \(b\) 分组,将所有 \(b\) 相同的分在一组,每一组内做一次 01 背包,\(f_{i,j}\) 表示当前 \(b=i\),背包容量为 \(j\times 2^b,j\in [0,10\times n]\) 时的最大价值。
接下来就需要考虑如何合并背包,注意到既然我们按照 \(b\) 也就是二进制位分组了,那么背包的合并也肯定还是按照二进制分组,类似的设 \(g_{i,j}\) 表示当前选取了 \(b=0\sim i\) 这些背包,\(b=i\) 这一组一共选择的背包容量为 \(j\times 2^i\),剩下的 \(0\sim i-1\) 这些组的背包选择的容量和 \(m\) 二进制低 \(i-1\) 位相同。
则有转移方程:
\[g_{i,j}=\max\{f_{i,j-k}+g_{i-1,\min\{10\times n,2\times k+((m>>(i-1))\&1)\}}\} \]解释就是考虑进位问题,从 \(i\) 位中选取 \(j-k\) 个,剩下的 \(k\) 个从 \(i-1\) 位进位而来,后面那一坨位运算就是考虑这一位进位完之后是 0 还是 1。
最后答案就是 \(g_{\lfloor\log_2m\rfloor,1}\)。
注意多测清空和开 long long。
Code:
/*
========= Plozia =========
Author:Plozia
Problem:P3188 [HNOI2007]梦幻岛宝珠
Date:2022/11/11
========= Plozia =========
*/
#include <bits/stdc++.h>
typedef long long LL;
using std::vector;
const int MAXN = 100 + 5;
int n, m;
LL a[MAXN], b[MAXN], v[MAXN], f[35][MAXN * 10], g[35][MAXN * 10];
vector <int> p[MAXN];
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
LL Max(LL fir, LL sec) { return (fir > sec) ? fir : sec; }
void Solve()
{
for (int i = 0; i <= 30; ++i) p[i].clear();
memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
for (int i = 1; i <= n; ++i)
{
int w = Read(); v[i] = Read();
for (int j = 30; j >= 0; --j)
if (w % (1 << j) == 0 && w / (1 << j) <= 10) { a[i] = w / (1 << j), b[i] = (1 << j); p[j].push_back(i); break ; }
}
for (int i = 0; i <= 30; ++i)
{
for (int j = 0; j < p[i].size(); ++j)
for (int k = 10 * n; k >= a[p[i][j]]; --k)
f[i][k] = Max(f[i][k], f[i][k - a[p[i][j]]] + v[p[i][j]]);
}
for (int i = 0; i <= 10 * n; ++i) g[0][i] = f[0][i];
for (int i = 1; i <= 30; ++i)
{
for (int j = 0; j <= 10 * n; ++j)
for (int k = 0; k <= j; ++k)
g[i][j] = Max(g[i][j], f[i][j - k] + g[i - 1][std::min(2 * k + ((m >> (i - 1)) & 1), 10 * n)]);
}
printf("%lld\n", g[std::__lg(m)][1]);
}
int main()
{
while (1) { n = Read(), m = Read(); if (n == -1) break ; Solve(); } return 0;
}
标签:10,梦幻岛,int,题解,P3188,times,ch,背包,MAXN
From: https://www.cnblogs.com/Plozia/p/16881614.html