金明的预算方案(DP)

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N], f[N];
int n, m, cnt = 1;  
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++){
		int v, p, q;
		cin >> v >> p >> q;
		if(!q){
			a[cnt] = v * p;
			b[cnt ++] = v;
		}
		else{
			b[q] += v;
			a[q] += v * p;
		}
	}
	for(int i = 1; i <= cnt; i ++)
		for(int j = n; j >= b[i]; j --)
			f[j] = max(f[j],f[j-b[i]] + a[i]);
	cout << f[n];

	return 0;
}