公元某年的猫 @ 2018-05-14 19:17:57
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 32001, M = 61;
struct object {
int v, p, q;
} o[M];
int n, m, dp[M][N], belong[M][2];
bool judge[M];
int main() {
scanf("%d%d", &n, &m);
int i, j, x, y, z, temp = 0;
for (i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
o[i].v = x, o[i].p = x*y, o[i].q = z;
if (z == 0) judge[i] = true;
else {
if (!belong[o[i].q][1]) belong[o[i].q][1] = i;
else belong[o[i].q][2] = i;
}
}
for (i = 1; i <= m; i++) {
if (!judge[i]) continue;
for (j = n; j >= o[i].v; j--) {
dp[i][j] = max(dp[temp][j], dp[temp][j-o[i].v]+o[i].p);
if (j-o[belong[i][1]].v-o[i].v >= 0) dp[i][j] = max(dp[temp][j], dp[temp][j-o[belong[i][1]].v-o[i].v]+o[belong[i][1]].p+o[i].p);
if (j-o[belong[i][2]].v-o[i].v >= 0) dp[i][j] = max(dp[temp][j], dp[temp][j-o[belong[i][2]].v-o[i].v]+o[belong[i][2]].p+o[i].p);
if (j-o[belong[i][1]].v-o[belong[i][2]].v-o[i].v >= 0) dp[i][j] = max(dp[temp][j], dp[temp][j-o[belong[i][1]].v-o[belong[i][2]].v-o[i].v]+o[belong[i][1]].p+o[belong[i][2]].p+o[i].p);
}
temp = i;
}
printf("%d", dp[temp][n]);
return 0;
}
by 公元某年的猫 @ 2018-05-14 19:18:50
为什么呢60分呢?求orz