没有降维，不会用stl所以马蜂像shift一样……用的是结构体=(

玄1关？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
int n,m,a,b,c[1001],k1=1,dp[1001][1001];
struct bag
{
	int v[1001],w[1001],k2;
}s[1001];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b>>c[i];
		if(c[i]!=c[i-1]) k1=1;
		s[c[i]].w[k1]=a;
		s[c[i]].v[k1]=b;
		s[c[i]].k2++;
		k1++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			int max2=-1;
			for(int k=1;k<=s[c[i]].k2;k++)
			{
				if(j>=s[i].w[k])
				{
					if(dp[i-1][j-s[i].w[k]]+s[i].v[k]>max2) max2=dp[i-1][j-s[i].w[k]]+s[i].v[k];
				}
			}
			dp[i][j]=max(dp[i-1][j],max2);
		}
	}
	cout<<dp[n][m];
}