logs hdu str 方程 维护 中文 %d r++ i++
题目大意:中文题面。。
二维01背包问题,给出所需经验值、忍耐度、种数、最大个数四个基本值,于是我们可以将最大个数作为第一维,第二维有两种维护方法,这里就给出将经验值作为第二维维护有关忍耐度的背包的做法吧。。
f[s][n]代表有s个怪,此时经验值为n,因为经验值可能会溢出,所以将上限上调20点,即第二维下标最大为n+20。
初始赋值-1,对0怪0经验即f[0][0]赋值忍耐度m,并且能得到状态转移方程f[i][j]=max(f[i-1][j-a[k]]-b[k]);
最后求解答案时将n到n+20这个经验值区间内所有怪的个数的忍耐度求个最大值,就能得到答案了。
- #include < cstdio > #include < cstring > int f[125][125],
- n,
- m,
- k,
- s,
- w[105],
- v[105],
- ans;
- int main() {
- while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
- for (int i = 1; i <= k; i++) scanf("%d%d", &w[i], &v[i]);
- memset(f, -1, sizeof(f));
- f[0][0] = m;
- for (int i = 1; i <= k; i++) for (int j = 1; j <= s; j++) for (int r = w[i]; r <= n + 20; r++) {
- if (f[j][r] < f[j - 1][r - w[i]] - v[i]) f[j][r] = f[j - 1][r - w[i]] - v[i];
- }
- ans = -1;
- for (int i = 1; i <= s; i++) for (int j = n; j <= n + 20; j++) if (ans < f[i][j]) ans = f[i][j];
- printf("%d\n", ans);
- }
- }
HDU 2159
来源: http://www.bubuko.com/infodetail-2348728.html