本人水平有限，题解不到为处，请多多谅解
本蒟蒻谢谢大家观看
题目：传送门
分组背包的模板：
伪代码：
1 for(int i=1;i<=组数;i++){ 2 for(int j=容量;j>=0;j--){ 3 for(int k=1;k<=每组的物品数;k++){ 4 f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); 5 } 6 } 7 }
直接套模板即可。
code:
1 #include<bits/stdc++.h> 2 #pragma GCC optimize(3) 3 const int N=1e5+10; 4 using namespace std; 5 int n,m; 6 int f[N],a[N],b[N],c[N],x,num; 7 int dp[1001][1001]; 8 inline int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 11 while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 12 return x*f; 13 } 14 inline void write(int x) 15 { 16 if(x<0)x=-x,putchar('-'); 17 if(x>9)write(x/10); 18 putchar(x%10+'0'); 19 } 20 int main() 21 { 22 m=read(),n=read(); 23 for(int i=1;i<=n;i++){ 24 a[i]=read(),b[i]=read(),x=read(); 25 num=max(x,num); 26 ++c[x];//算每组的个数 27 dp[x][c[x]]=i;//求第i组第j个的编号 28 } 29 memset(f,0,sizeof(f)); 30 f[0]=0;//最好初始化 31 for(int i=1;i<=num;i++){ 32 for(int j=m;j>=0;j--){ 33 for(int k=1;k<=c[i];k++){ 34 if(j>=a[dp[i][k]]){ 35 f[j]=max(f[j],f[j-a[dp[i][k]]]+b[dp[i][k]]);//套模板即可 36 } 37 } 38 } 39 } 40 printf("%d\n",f[m]); 41 return 0; 42 }