题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
思路：
首先对输入分组，每组包含一个主要的和可能有的附加物品，使用一个vector记录主要物品的idx，再使用两个vector存放价格和满意度（二维的数组，三列，第一列是主物品，二三是附加，如果没有为0）；
之后构建dp矩阵，当前值为max（上一格的值， 当前主物品+附加品的四个状态的满意度+剩余钱上一行对应的满意度）。
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main(){
int N,m;
cin>>N>>m;
N /= 10;
vector<int> idx;
vector<vector<int>> price(m+1,vector<int>(3,0));
vector<vector<int>> weight(m+1,vector<int>(3,0));
for(int i = 1; i<=m; ++i){
int a,b,c;
cin >> a >> b >> c;
a /= 10; b *= a;
if(c == 0){
price[i][0] = a; weight[i][0] = b;
idx.push_back(i);
}else{
if(price[c][1] == 0) {
price[c][1] = a; weight[c][1] = b;
}else{
price[c][2] = a; weight[c][2] = b;
}
}
}
int size = idx.size();
vector<vector<int>> dp(size+1, vector<int>(N+1,0));
for(int i = 1; i <= size; ++i){
int id = idx[i-1];
int a = price[id][0], b = weight[id][0];
int c = price[id][1], d = weight[id][1];
int e = price[id][2], f = weight[id][2];
for(int j = 1; j<= N; ++j){
dp[i][j] = dp[i-1][j];
if(a+c+e<=j) dp[i][j] = max((b+d+f) + dp[i-1][j-a-c-e],dp[i][j]);
if(a+c<=j) dp[i][j] = max((b+d) + dp[i-1][j-a-c],dp[i][j]);
if(a+e<=j) dp[i][j] = max((b+f) + dp[i-1][j-a-e],dp[i][j]);
if(a<=j) dp[i][j] = max((b) + dp[i-1][j-a],dp[i][j]);
}
}
cout<<dp[size][N]*10<<endl;
return 0;
}
查看10道真题和解析