-v- 话说，虽然NOIP拿了一等奖，但至今还没把联赛题做一遍（普及组还有几个一直没做）。

最近想补补动态规划、递推之类的，先拿些简单的背包练练。

金明的预算方案（提高组），题目就不贴了。不算难的背包问题，就是在基本的0/1背包上加了一个简单的主/附件依赖。由于依赖关系很简单，每个主件最多被两个附件依赖，动规转移时用几个IF语句找下列情况最优的一个即可：

1.不选该主件及附件  2.只选主件  3.选主件和第一个附件  4.选主件和第二个附件  5.选主件和两个附件

以下是C++代码。直接用了背包的降维，动规中的那写IF语句为了减少重复运算做了优化，可能有点难看。

#include <fstream>
#include <cstring>

using namespace std;

int main ()
{
	ifstream fin("budget.in");
	ofstream fout("budget.out");

	int N, M;
	fin >> N >> M;
	int V[M][3], P[M][3];

	memset(V, 0, sizeof(V));
	memset(P, 0, sizeof(P));
	for (int i=0; i<M; i++)
	{
		int v, p, q;
		fin >> v >> p >> q;
		if (q)
			if (!V[q-1][1])
				V[q-1][1] = v,
				P[q-1][1] = p;
			else
				V[q-1][2] = v,
				P[q-1][2] = p;
		else
			V[i][0] = v,
			P[i][0] = p;
	}

	int f[N+1];
	memset(f, 0, sizeof(f));
	for (int i=0; i<M; i++)
		if (V[i][0])
			for (int j=N; j>=V[i][0]; j--)
			{
#define T(X) (V[i][X]*P[i][X])
				int rest = j-V[i][0], sum = T(0);

				if (f[rest] + sum > f[j])
					f[j] = f[j-V[i][0]] + sum;

				if (rest-V[i][1] >= 0  &&
						f[rest-V[i][1]] + sum + T(1) > f[j])
					f[j] = f[rest-V[i][1]] + sum + T(1);

				if ((rest = rest-V[i][2]) >= 0)
				{
					if (f[rest] + (sum = sum + T(2)) > f[j])
						f[j] = f[rest] + sum;

					if ((rest = rest-V[i][1]) >= 0)
						if (f[rest] + (sum = sum + T(1)) > f[j])
							f[j] = f[rest] + sum;
				}
			}

	int ans = 0;
	for (int i=1; i<=N; i++)
		if (f[i] > ans)
			ans = f[i];

	fout << ans << endl;

	fin.close();
	fout.close();

	return 0;
}