我们注意每个dp【j】可以从dp【j-v】+ w...dp【j-k*v】+k*w转移过来，那个他们的公差是v，我们可以以对v的余数来把他们
划分成几个小组，比如背包总容量为10，这个物品的体积为3，那么我们可以把0到10划分成｛0，3，6，9｝，｛1，4，7，10｝，｛2，5，8｝，
我们可以发现不同小组的是不会影响的，因为他们每个的距离都不是3的整数倍。那么对于每个小组的话，我们就可以维护dp【j-k*v】+k*w最大
，相当于我们维护一个递减的序列，然后每次要判断合不合法，就是j-c是否大于a【l】，（说明a【l】这个物品的数量不够到达 j //现在先这么理解吧，可能有错）
然后每次对首都是最大的，
#include <bits/stdc++.h> int a[1005],b[1005],dp[100005]; int w,v,c,n,V,l,r; void insert(int x,int y) { while(l<=r&&b[r]<=y)r--; a[++r]=x;b[r]=y; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&V,&n); int i,j,d; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d%d",&v,&w,&c); for(d=0;d<v;d++) { l=1; r=0; for(j=0;j<=(V-d)/v;j++) { insert(j,dp[j*v+d]-j*w); if(a[l]<j-c)l++; dp[j*v+d]=b[l]+j*w; } } } printf("%d ",dp[V]); } return 0; }