60分求救...只统计主件,不统计附件

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

pqy000 @ 2018-09-19 11:59:06

#include<iostream>
#include<algorithm>
using namespace std;
#define MMAX 65
#define NMAX 32005

int v[MMAX][3], p[MMAX][3], N, M;
int thing[NMAX];

int cost2(int index, int x) { return v[index][0] + v[index][x]; }
int cost3(int index, int x, int y)
{ return v[index][0] + v[index][x] + v[index][y]; }
int value(int index, int x){ return v[index][x] * p[index][x]; }

int main() {
    scanf("%d%d", &N, &M);
    int _v, _p, _q;
    int num = 1;
    for(int i = 1; i <= M; i++) {
        scanf("%d%d%d", &_v, &_p, &_q);
        if(_q == 0) {
            v[num][0] = _v; p[num][0] = _p;
            num += 1;
        } else {
            if(v[_q][1] == 0) {
                v[_q][1] = _v; p[_q][1] = _p;
            } else {
                v[_q][2] = _v; p[_q][2] = _p;
            }
        }
    }

    for(int i = 1; i < num; i++) {
        for(int j = N; j >= 0; j--) {
            if(j >= v[i][0]){
                thing[j] = max(thing[j], thing[j - v[i][0]] + value(i, 0) ); }
            if(j >= (v[i][0] + v[i][1]) && v[i][1] != 0 ) {
                thing[j] = max(thing[j], thing[j - v[i][0] - v[i][1] ] + v[i][0] * p[i][0] + v[i][1] * p[i][1]);
            }
            if(j >= (v[i][0] + v[i][2]) && v[i][2] != 0 ) {
                thing[j] = max(thing[j], thing[j - v[i][0] - v[i][2]] + v[i][0] * p[i][0] + v[i][2] * p[i][2]);
            }
            if(j >= (v[i][0] + v[i][1] + v[i][2]) && v[i][1] != 0 && v[i][2] != 0) {
                thing[j] = max(thing[j], thing[j - (v[i][0] + v[i][1] + v[i][2])]
                               + v[i][0] * p[i][0] + v[i][1] * p[i][1] + v[i][2] * p[i][2]);
            }
        }
    }
    /*
    for(int i = 1; i < num; i++) {
        for(int j = 0; j < 3; j++) {
            printf("(%d %d) ", v[i][j], p[i][j]);
        }
        printf("\n");
    } */

    //for(int i = 1; i <= N; i++) { printf("%d %d\n", i, thing[i]); }

    printf("%d\n", thing[N]);

    return 0;
}

转移方程也写好了....在本题中我只存储了主件,附件直接挂靠在主件上,并统计遍历主件的数量num,但结果是错的...我想了解下怎样改进,谢谢大佬, 不过的样例如下:

//input
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

//output
7430
//程序错误输出
7200

谢谢诸位大佬~


|