【HDOJ】3732 Ahui Writes Word

时间:2021-07-28 07:55:45

初看01背包,果断TLE。是因为n和C都比较大。但是vi和ci却很小,转化为多重背包。

 #include <cstdio>
#include <cstring> int map[][];
int dp[];
int n, C; int max(int a, int b) {
return a>b ? a:b;
} void ZeroOnePack(int v, int c) {
for (int i=C; i>=c; --i)
dp[i] = max(dp[i-c]+v, dp[i]);
} void CompeletePack(int v, int c) {
for (int i=c; i<=C; ++i)
dp[i] = max(dp[i-c]+v, dp[i]);
} void MultiPack(int v, int c, int k) {
if (c*k >= C) {
CompeletePack(v, c);
return ;
}
int r = ;
while (r < k) {
ZeroOnePack(r*v, r*c);
k = k - r;
r <<= ;
}
ZeroOnePack(k*v, k*c);
} int main() {
int v, c;
char s[];
int i, j; while (scanf("%d %d", &n, &C) != EOF) {
memset(map, , sizeof(map));
memset(dp, , sizeof(dp));
for (i=; i<n; ++i) {
scanf("%s %d %d", s, &v, &c);
map[v][c]++;
}
for (i=; i<=; ++i) {
for (j=; j<=; ++j) {
if (map[i][j])
MultiPack(i, j, map[i][j]);
}
}
printf("%d\n", dp[C]);
} return ;
}