【金明的预算方案】 （C++代码）

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 7;
int Fir_v[MAXN];
int Fir_w[MAXN];
int Sec_v[MAXN][3];
int Sec_w[MAXN][3];
int dp[MAXN];
int main()
{
	int N, M;
	cin >> N >> M;
	int v, p, q;
	for (int i = 1; i <= M; i++)
	{
		cin >> v >> p >> q;
		if (!q)
		{
			Fir_v[i] = v;
			Fir_w[i] = v * p;
		}
		else
		{
			Sec_v[q][0]++;
			Sec_v[q][Sec_v[q][0]] = v;
			Sec_w[q][Sec_v[q][0]] = v * q;
		}
	}
	for (int i = 1; i <= M; i++)
	{
		for (int j = N; j >= Fir_v[i] && Fir_v[i] != 0; j--)
		{
			dp[j] = max(dp[j], dp[j - Fir_v[i]] + Fir_w[i]);
			if (j >= Fir_v[i] + Sec_v[i][1])
			{
				dp[j] = max(dp[j], dp[j - Fir_v[i] - Sec_v[i][1]] + Fir_w[i] + Sec_w[i][1]);
			}
			if (j >= Fir_v[i] + Sec_v[i][2])
			{
				dp[j] = max(dp[j], dp[j - Fir_v[i] - Sec_v[i][2]] + Fir_w[i] + Sec_w[i][2]);
			}
			if (j >= Fir_v[i] + Sec_v[i][2] + Sec_v[i][1])
			{
				dp[j] = max(dp[j], dp[j - Fir_v[i] - Sec_v[i][2] - Sec_v[i][1]] + Fir_w[i] + Sec_w[i][2] + Sec_w[i][1]);
			}
		}
	}
	cout << dp[N] << endl;
	return 0;
}