[USACO09DEC] Video Game Troubles

背包DP；有依赖的背包问题

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

int n, V;

int f[2][100003];

int main() {

	scanf("%d%d", &n, &V);

	for (int i=1, P, G; i<=n; ++i) {

		scanf("%d%d", &P, &G);

		for (int j=V; j>=P; --j) f[i&1][j]=f[(i-1)&1][j-P]; // suppose we have to buy it

		for (int j=1, w, c; j<=G; ++j) {

			scanf("%d%d", &c, &w);

			for (int k=V; k>=c+P; --k) f[i&1][k]=max(f[i&1][k], f[i&1][k-c]+w);

		}

		for (int j=V; j>=0; --j) f[i&1][j]=max(f[(i-1)&1][j], f[i&1][j]); // revise

	}

	printf("%d\n", f[n&1][V]);

	return 0;

}

巴特西

[USACO09DEC] Video Game Troubles

最新文章

热门文章