题解 | #购物单#

//我的暴力动态规划
//思路就是，先把里面有哪些主件和附件按顺序记录下来，然后按照主件去遍历
//如果说一个个按照输入去遍历，当访问到附件的时候就要去找主件，我一直想不通怎么解决一个主件被重复计算的问题
//所以干脆直接重新建了一个数据结构，有点憨批但是过了。
int main()
{
	int N, m;
	cin >> N >> m;
	N /= 10;
	int * v = new int[m];
	int * p = new int[m];
	int * q = new int[m];

	int MainCount = 0;
	for (int i = 0; i<m; ++i) {
		cin >> v[i] >> p[i] >> q[i];
		v[i] /= 10;
	}
	//最多一个主键两个附件,最后一个位置存原id
	vector<vector<int>> table(m+1, vector<int>(6, 0));
	//先存主键
	vector<int> mainid;
	for (int i = 1; i<m+1; ++i) {
		if (q[i-1] == 0) {
			table[i][0] = v[i-1];
			table[i][1] = v[i-1] * p[i-1];
			mainid.emplace_back(i);
		}
	}
	//再存附件
	for (int i = 1; i<m + 1; ++i) {
		if (q[i-1] != 0) {
			if (table[q[i-1]][2] == 0) {
				table[q[i-1]][2] = v[i-1];
				table[q[i-1]][3] = v[i-1] * p[i-1];
			}
			else {
				table[q[i-1]][4] = v[i-1];
				table[q[i-1]][5] = v[i - 1] * p[i - 1];
			}
		}
	}

	vector<vector<int>> dp(m+1, vector<int>(N+1, 0));
	int i = mainid[0];
	for (int j = table[i][0]; j<N + 1; ++j) {
		//只有主键
		if ((j - table[i][0]) >= 0) {
			dp[i][j] = table[i][1];
		}
		//只有主键+附件一
		if (table[i][2] != 0 && (j - table[i][0] - table[i][2]) >= 0) {
			dp[i][j] = max(table[i][1] + table[i][3], dp[i][j]);
		}
		//只有主键+附件二
		if (table[i][4] != 0 && (j - table[i][0] - table[i][4]) >= 0) {
			dp[i][j] = max(table[i][1] + table[i][5], dp[i][j]);
		}
		//有附件一、二
		if (table[i][4] != 0 && (j - table[i][0] - table[i][2] - table[i][4]) >= 0) {
			dp[i][j] = max(table[i][1] + table[i][3] + table[i][5], dp[i][j]);
		}
	}
	for (int id = 1; id < mainid.size();++id) {
		int i = mainid[id];
		for (int j = 1; j<N+1; ++j) {
			dp[i][j] = dp[mainid[id - 1]][j];
			//只有主键
			if ((j - table[i][0]) >= 0) {
				dp[i][j] = max(dp[mainid[id - 1]][j - table[i][0]] + table[i][1], dp[i][j]);
			}
			//只有主键+附件一
			if (table[i][2] != 0 && (j - table[i][0] - table[i][2]) >= 0) {
				dp[i][j] = max(dp[mainid[id - 1]][j - table[i][0] - table[i][2]] + table[i][1] + table[i][3], dp[i][j]);
			}
			//只有主键+附件二
			if (table[i][4] != 0 && (j - table[i][0] - table[i][4]) >= 0) {
				dp[i][j] = max(dp[mainid[id - 1]][j - table[i][0] - table[i][4]] + table[i][1] + table[i][5], dp[i][j]);
			}
			//有附件一、二
			if (table[i][4] != 0 && (j - table[i][0] - table[i][2] - table[i][4]) >= 0) {
				dp[i][j] = max(dp[mainid[id - 1]][j - table[i][0] - table[i][2] - table[i][4]] + table[i][1] + table[i][3] + table[i][5], dp[i][j]);
			}
		}
	}
	cout << dp[mainid[mainid.size()-1]][N] * 10 << endl;

	return 0;
}