题解 | #购物单#

该解法的思路是将主件p、主件v,附件1p、附件1v,附件2p、附件2v共6个数据作为一组存储（为什么一开始没想到用二维数组呢ORZ） 这样如果是10件物品，总共需要60个空间，用load函数放与pvp1v1p2v2数组中（非常形象的数组名）。onedp函数算出每一次dp的最大价值，这里需要两个dp数组比如100元，第一件物品80元，第二件物品20元，这样算100元买第二件物品的时候价值就会加上80元的价值。 该解法还可以继续稍作优化，因为比如第二行物品是第一行物品的附件的话，pvp1v1p2v2[6-11]全是INVALID，可以把这种空间“压缩”掉。

#define INVALID -1
#define mMAX 60
#define NMAX 3200//多少个“10元”
#include<stdio.h>

void load(int*arr,int num,int p,int v,int q){//物品数组arr,第num件物品从1开始，价格p，价值v,主件编号q
    int start=q==0?6*(num-1):6*(q-1);
    if(q!=0)
        start+=arr[start+2]==INVALID?2:4;//如果是附件，就往后移2位（第一件附件），或4位（第二件附件）
    arr[start]=p/10;
    arr[++start]=v;
}
int onedp(int* pvp1v1p2v2,int* dp,int money,int value,int j){//这么多钱，第j件物品，要买不买，给个最大值
    int max=value,*p=pvp1v1p2v2+6*(j-1);
    if(*p==INVALID||money<*p)//主件没有或者买不了
        return max;
    value=dp[money-*p]+*p**(p+1);//只买主件
    max=max>value?max:value;
    value=max;
    money-=*p;
    if(*(p+2)!=INVALID&&money>=*(p+2))//买了主件后，可买附件1
        value=dp[money-*(p+2)]+*p**(p+1)+*(p+2)**(p+3);//主+附1
    max=max>value?max:value;
    if(*(p+4)!=INVALID&&money>=*(p+4))//买了主件后，可买附件2
        value=dp[money-*(p+4)]+*p**(p+1)+*(p+4)**(p+5);//主+附2
    max=max>value?max:value;
    if(*(p+2)!=INVALID&&*(p+4)!=INVALID&&money>=(*(p+2)+*(p+4)))
        value=dp[money-*(p+2)-*(p+4)]+*p**(p+1)+*(p+2)**(p+3)+*(p+4)**(p+5);//主+附1+附2
    max=max>value?max:value;
    return max;
}
int main(){
    int pvp1v1p2v2[6*mMAX],N,m;
    for(int i=0;i<6*mMAX;i++)
        pvp1v1p2v2[i]=INVALID;//初始化
    scanf("%d%d",&N,&m);
    N/=10;//现在N表示有多少个“10元”
    int price,value,q,num=1;
    while(scanf("%d%d%d",&price,&value,&q)!=EOF){
        load(pvp1v1p2v2,num,price,value,q);
        num++;
    }
    int dp1[NMAX],dp2[NMAX],* dp_now=dp1,* dp_pre=dp2,j,money=0;
    dp1[0]=0,dp2[0]=0;
    for(j=1;j<=m;j++){
        while(j<=m&&pvp1v1p2v2[6*(j-1)]==INVALID)j++;//跳过主件是空的情况
        if(j>m)break;
        for(money=1;money<=N;money++)
            dp_now[money]=onedp(pvp1v1p2v2,dp_pre,money,dp_pre[money],j);
        int* temp=dp_now;
        dp_now=dp_pre;
        dp_pre=temp;
    }
    printf("%d\n",10*dp_pre[N]);
}