【DP】 HDOJ 5410 CRB and His Birthday

まず01リュックサックを作って、もう一度多重リュックサックを作ります.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2005;
int dp[maxn];

void work()
{
	int n, m;
	memset(dp, 0, sizeof dp);
	scanf("%d%d", &n, &m);
	while(m--) {
		int a, b, c;
		scanf("%d%d%d", &c, &a, &b);
		for(int i = n; i >= c; i--) dp[i] = max(dp[i], dp[i-c] + a + b);
		for(int i = c; i <= n; i++) dp[i] = max(dp[i], dp[i-c] + a);
	}
	printf("%d
", dp[n]);
}

int main()
{
	int _;
	scanf("%d", &_);
	while(_--) work();
	
	return 0;
}