T2 P2306 被 yyh 虐的 mzc
传送门:洛谷P2306
很显然的一道背包,但是 \(n,m<= 1e5\) ,普通的背包会 T 飞,怎么办呢。。。
认真看一下数据规模,\(a[i],b[i] <= 10\) 那么 \(a[i],b[i]\) 组合最多\(100\)种不同的家丁,说明会有重复,那么我们把所有重复的记在 \(t[a[i]][b[i]]\) 中,那这样就变成了数据规模为 \(100\) 的多重背包,但是 \(m<=1e5\) ,所以我们还需要多重背包二进制优化,不会的可以看看这个:
多重背包二进制优化
那这样代码就简单了;
贴代码:
#include <bits/stdc++.h>
using namespace std;
const int maxm = 1e5 + 5;
int t[11][11], dp[maxm], tot, n, m, k, w[maxm], c[maxm];
struct Grou {
int w, c, k;
} g[105];
void read() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++ i) {
scanf("%d%d", &w[i], &c[i]);
if (!t[w[i]][c[i]]) {
t[w[i]][c[i]] = ++ tot;
g[tot].c = c[i], g[tot].w = w[i], g[tot].k = 1;
}
else g[t[w[i]][c[i]]].k ++;
}
for (int i = 1; i <= tot; ++ i) {
int j = 1;
for (j = 1; j <= g[i].k; g[i].k -= j, j <<= 1) {
for (int v = m; v >= j * g[i].w; -- v) {
dp[v] = max(dp[v], dp[v - j * g[i].w] + j * g[i].c);
}
}
if (g[i].k) {
for (int v = m; v >= g[i].k * g[i].w; -- v)
dp[v] = max(dp[v], dp[v - g[i].k * g[i].w] + g[i].k * g[i].c);
}
}
if (dp[m] < k) printf("no\n");
else printf("yes\n");
printf("%d\n", dp[m]);
}
int main() {
read();
return 0;
}
标签:背包,17,int,2023.04,printf,T2,maxm,dp
From: https://www.cnblogs.com/florence25/p/17327899.html