#include<bits/stdc++.h>
using namespace std;
long long n,m,v,p,q,mw[10010],mv[10010],fv[10010][10010],f[10010],fw[10010][10010];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>v>>p>>q;
		if(!q){
			mw[i]=v;mv[i]=v*p;}
		else{
			fw[q][0]++;fw[q][fw[q][0]]=v;fv[q][fw[q][0]]=v*p;}}
	for(int i=1;i<=m;i++)
		for(int j=n;j>=mw[i];j--){ 
	        f[j]=max(f[j],f[j-mw[i]]+mv[i]); 
	        if(j>=mw[i]+fw[i][1]) f[j]=max(f[j],f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]);
	        if(j>=mw[i]+fw[i][2]) f[j]=max(f[j],f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]);
	        if(j>=mw[i]+fw[i][1]+fw[i][2]) f[j]=max(f[j],f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);}
    cout<<f[n];
	return 0;}

不压行：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,v,p,q,mw[10010],mv[10010],fv[10010][10010],f[10010],fw[10010][10010];
main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>v>>p>>q;
		if(!q)
		{
			mw[i]=v;
			mv[i]=v*p;
		}
		else
		{
			fw[q][0]++;
			fw[q][fw[q][0]]=v;
			fv[q][fw[q][0]]=v*p;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=mw[i];j--)
		{ 
	        f[j]=max(f[j],f[j-mw[i]]+mv[i]); 
	        if(j>=mw[i]+fw[i][1])
			{
	        	f[j]=max(f[j],f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]);
			}
	        if(j>=mw[i]+fw[i][2])
			{
				f[j]=max(f[j],f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]);
			} 
	        if(j>=mw[i]+fw[i][1]+fw[i][2])
			{
	        	f[j]=max(f[j],f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);
			} 
	    }
	}
    cout<<f[n];
	return 0;
}

awa