#include "stdio.h"
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
int main() { int N = 0, m = 0; int value[60][3] = { 0 }; int weight[60][3] = { 0 }; int dp[60][3200] = { 0 }; int v, p, q; while (scanf("%d%d", &N, &m) != -1) { N /= 10; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &v, &p, &q); v /= 10; if (q == 0) { value[i][0] = v; weight[i][0] = v*p; } else { if (value[q][1] == 0) /* 这里q代表属于主件的编号，例如q=1,即该附件属于编号1的主件，又因为一个主件至多有两个附件，所以这里进行判断。如果有一个了，就放第二个附件的位置。*/ { value[q][1] = v; weight[q][1] = v * p; } else { value[q][2] = v; weight[q][2] = v * p; } }
} for (int i = 1; i <= m; i++) for (int j = 1; j <= N; j++) { dp[i][j] = dp[i - 1][j]; /*先将前i-1件物品的乘积放入*/
if (j >= value[i][0]) dp[i][j] = MAX(dp[i][j], dp[i - 1][j - value[i][0] ] + weight[i][0]);
/* 这个很多人 写成 dp[i][j] = MAX(dp[i-1][j], dp[i - 1][j - value[i][0] ] + weight[i][0]);
注意看跟上面的差别在于，MAX里面第一项变成了dp[i-1][j]，导致后续的比值都是跟不放物品比较，容易造成前面的大值被后面的小值覆盖。
例如dp[i-1][j] = 800；
第一个if算出来放物品得到1000，所以dp[i][j] = MAX(800, 1000) = 1000;
第二个if算出来放物品得到900，所以dp[i][j] = MAX(800, 900) = 900;
发现了吗，第一个的大值被第二个小值取代了，因为dp[i][j]始终取当前两个中的最大值，而dp[i-1][j]始终是一个值，这就是MAX()里面要用dp[i][j]而不用dp[i-1][j]的原因。
*/
if (j >= (value[i][0] + value[i][1])) dp[i][j] = MAX(dp[i][j], dp[i - 1][j - (value[i][0] + value[i][1])] + weight[i][0] + weight[i][1]);
if (j >= (value[i][0] + value[i][2])) dp[i][j] = MAX(dp[i][j], dp[i - 1][j - (value[i][0] + value[i][2])] + weight[i][0] + weight[i][2]);
if (j >= (value[i][0] + value[i][1] + value[i][2])) dp[i][j] = MAX(dp[i][j], dp[i - 1][j - (value[i][0] + value[i][1] + value[i][2])] + weight[i][0] + weight[i][1] + weight[i][2]); } printf("%d\n", dp[m][N]*10); } }
