20分代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,a[1010],b[1010],c[1010],dp[1010],f[1010],p[1010];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=m;i++)
for(int j=n;j>=b[i];j--)
{
if(f[c[i]]==0)
{
if(dp[j-b[i]]+a[i]>dp[j])
{
dp[j]=dp[j-b[i]]+a[i];
p[i]=a[i];
f[c[i]]=1;
}
}
else
{
if(dp[j-b[i]]-p[i]+a[i]>dp[j])
{
dp[j]=dp[j-b[i]]-p[i]+a[i];
p[i]=a[i];
}
}
}
cout<<dp[n];
return 0;
}