题解 | #购物单#

#include<vector>
using namespace std;
int main(){
    int N,m;//可以看成0-1背包问题，N是总价格，可以看成背包容量。
    cin>>N>>m;
    N/=10;//因为价格都是10的倍数，所以可以除以10来减少循环次数。
    //一个主件最多可以有两个配件，在第0号位存主件，1号位存1号配件，2号位存2号配件。
    vector<vector<int>> price(m+1,vector<int>(3,0));
    vector<vector<int>> value(m+1,vector<int>(3,0));
    for(int i=1;i<=m;i++){
        int v,p,q;
        cin>>v>>p>>q;
        if(q==0){//如果是主件，就在price[i]的0号位记录下
            price[i][0]=v/10;
            value[i][0]=p;
        }
        else{//如果是配件，查对应的主件，如果主件一号位是空的，就放在一号位。
            if(price[q][1]==0){
                price[q][1]=v/10;
                value[q][1]=p;
            }
            else{
                price[q][2]=v/10;
                value[q][2]=p;
            }
        }
    }
    vector<vector<int>> dp(m+1,vector<int>(N+1,0));//构造dp数组
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=N;j++){
            int a=price[i][0],b=value[i][0];
            int c=price[i][1],d=value[i][1];
            int e=price[i][2],f=value[i][2];
            if(j>=a){
                dp[i][j]=max(dp[i-1][j-a]+a*b,dp[i-1][j]);//如果能放进去主件，就考虑是否放入主件的情况。
            }
            else{
                dp[i][j]=dp[i-1][j];//第i个主件不放进去。
            }
            //这时候如果可以再放入配件，就考虑放入配件的情况.注意放入配件的同时要放入主件。
            if(j>=a+c){
                dp[i][j]=max((dp[i-1][j-a-c]+a*b+c*d),dp[i][j]);
            }
            if(j>=a+e){
                dp[i][j]=max(dp[i-1][j-a-e]+a*b+e*f,dp[i][j]);
            }
            if(j>=a+e+c){
                dp[i][j]=max(dp[i-1][j-a-c-e]+a*b+c*d+e*f,dp[i][j]);
            }
        }
    }
    cout<<dp[m][N]*10<<endl;
}