题解 | #购物单#

#include <stdio.h>

#define MAX(a,b)   ((a)>(b))?(a):(b)
typedef unsigned int uint32_t;

void GetInput(void);
uint32_t SolveShopProb(int N, int m); //结果定义为uint32_t, 因为int类型最大为65535,可能溢出。

int main() {
    GetInput();
    return 0;
}

int V[61][3] = {0};
int VP[61][3] = {0};

//获取数据
void GetInput(void) {
    int N = 0;
    int m = 0;

    int v = 0;//输入缓存变量v、p、q
    int p = 0;
    int q = 0;

    scanf("%d %d", &N, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &v);
        scanf("%d", &p);
        scanf("%d", &q);
	    //输入合法性检查
        if(v%10 != 0)   perror("Input Error!");
        if(p<1 || p>5)  perror("Input Error!");
        if(q<0 || q>m)  perror("Input Error!");
    
	  	//输入数据规范化处理。（将附件设置在主件价格、重要度数组成员中）
        if (q == 0) {
            V[i][0] = v / 10;
            VP[i][0] = v * p;
        } else {
            if (V[q][1] != 0) 
            {
                V[q][2] = v / 10;
                VP[q][2] = v * p;
            } 
            else 
            {
                V[q][1] = v / 10;
                VP[q][1] = v * p;
            }
        }
    }
    long res = SolveShopProb(N, m);
    printf("%ld", res);
}



//运算部分
uint32_t SolveShopProb(int N, int m) {
    //uint32_t DP[3200];    //32000/10 = 3200，要初始化为0，否则里面一开始是很大的值。
    uint32_t DP[3200] ={0};

    //for (int i = 1; i <= m && V[i][0] != 0; i++) //跳过附件应该用 if--continue,不能在这里写&& V[i][0] != 0，因为这样会中断整个for循环，
    for (int i = 1; i <= m; i++) 
    {
        if(V[i][0] == 0) continue;//跳过附件
        for (int j = N / 10; j >= V[i][0]; j--)
        {
            //第零种情况：无法装下：DP[i]=DP[i]
            //第一种情况：只有主件
            uint32_t temp_max = DP[j - V[i][0]] + VP[i][0];
            DP[j] = MAX(DP[j], temp_max);

            //第二种情况：主件+附件1
            if (V[i][1] != 0) //如果有附件1
            {
                int vsum = V[i][0] + V[i][1];
                if (j >= vsum) {
                    temp_max = DP[j - vsum] + VP[i][0] + VP[i][1];
                }
                DP[j] = MAX(DP[j], temp_max);
			  
                if (V[i][2] != 0) //如果有附件2
                {
				  	//第三种情况：主件+附件2
                    vsum = V[i][0] + V[i][2];
                    if (j >= vsum) {
                        temp_max = DP[j - vsum] + VP[i][0] + VP[i][2];
                    }
                    DP[j] = MAX(DP[j], temp_max);

                    //第四种情况：主件+附件1+附件2
                    vsum = V[i][0] +V[i][1]+V[i][2];
                    if (j >= vsum) {
                        temp_max = DP[j - vsum] + VP[i][0] + VP[i][1]+ VP[i][2];
                    }
                    DP[j] = MAX(DP[j], temp_max);
                }
            }
        }
       // printf("when i=%d, DP[N/10]=%d\n", i,DP[N/10]);
    }
    return DP[N/10];
}