请问,有没用滚动数组做的吗?

P1064 [NOIP2006 提高组] 金明的预算方案

公元某年的猫 @ 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


|