简单dp,小蒟蒻A不了
查看原帖
简单dp,小蒟蒻A不了
461366
封禁用户楼主2021/7/27 08:03

只拿到了pts20,我什么地方错了

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

int a[65], b[65], pr[65], n, m;
int c[65][2], d[65][32005];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int v, p, q;
		scanf("%d%d%d", &v, &p, &q);
		a[i] = v * p;
		pr[i] = v;
		if (!c[q][0]) c[q][0] = i;
		else c[q][1] = i;
		b[i] = q;
	}
	for (int i = 1; i <= m; i++) {
		int p = b[i], ls = c[p][0], rs = c[p][1];
		for (int j = 0; j <= n; j++) {
			d[i][j] = d[i - 1][j];
			if (p) {
				if (pr[p] <= j) d[i][j] = max(d[i][j], d[i - 1][j - pr[p]] + a[p]);
				if (ls && pr[p] + pr[ls] <= j) d[i][j] = max(d[i][j], d[i - 1][j - pr[p] - pr[ls]] + a[p] + a[ls]);
				if (rs && pr[p] + pr[rs] <= j) d[i][j] = max(d[i][j], d[i - 1][j - pr[p] - pr[rs]] + a[p] + a[rs]);
				if (ls && rs && pr[p] + pr[ls] + pr[rs] <= j) d[i][j] = max(d[i][j], d[i - 1][j - pr[p] - pr[ls] - pr[rs]] + a[p] + a[ls] + a[rs]);
			} else if (pr[i] <= j) {
				d[i][j] = max(d[i][j], d[i - 1][j - pr[i]] + a[i]);
			}
		}
	}
	printf("%d\n", d[m][n]);
	return 0;
}
2021/7/27 08:03
加载中...