我的代码看起来没什么问题,但是为什么wa了4,6两个点QWQ
#include <bits/stdc++.h>
#include <set>
#include <vector>
using namespace std;
int n,m,dp[32005];
vector<vector<struct node> > f(65);
struct node
{
int v,p,q,idx;
}node[65];
bool cmp(struct node a,struct node b){
return a.q<b.q;
}
int main() {
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>node[i].v>>node[i].p>>node[i].q;
node[i].idx=i;
}
sort(node+1,node+1+m,cmp);
for(int i=1;i<=m;i++)
f[node[i].q].push_back(node[i]);
for(int i=0;i<f[0].size();i++) //遍历主件
{
for(int j=n;j>=1;j--)
{
int a=f[0][i].v,b=f[0][i].p,c=f[0][i].q,idx=f[0][i].idx;
if(a>j) continue;
if(dp[j]>dp[j-a]+a*b) continue; //不买直接continue
dp[j]=dp[j-a]+a*b; //买
if(f[idx].size()==0) continue; //没有附件直接continue
else if(f[idx].size()==1){ //一个附件
if(a+f[idx][0].v<=j){
dp[j]=max(dp[j],dp[j-a-f[idx][0].v]+a*b+f[idx][0].v*f[idx][0].p);
}
}else{ //两个附件
int r1=0,r2=0,r3=0;
if(a+f[idx][0].v<=j){
r1= dp[j-a-f[idx][0].v]+a*b+f[idx][0].v*f[idx][0].p;//买第一个附件
}
if(a+f[idx][1].v<=j){
r2= dp[j-a-f[idx][1].v]+a*b+f[idx][1].v*f[idx][1].p;//买第二个附件
}
//买两个附件
if(a+f[idx][0].v+f[idx][1].v<=j){
r3= dp[j-a-f[idx][0].v-f[idx][1].v]+a*b+f[idx][0].v*f[idx][0].p+f[idx][1].v*f[idx][1].p;
}
int res=max(r1,max(r2,r3));
dp[j]=max(dp[j],res);
}
}
// for(int k=1;k<=n;k++) cout<<dp[k]<<" ";
// cout<<endl;
}
cout<<dp[n];
return 0;
}