#include<iostream> using namespace std; long long w[10005],v[10005],s[10005],f[10005],m,n,idx=1; int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ int ww,vv,ss; cin>>ww>>vv>>ss; for(int j=1;j<=ss;j++){ w[idx]=ww; v[idx]=vv; idx++; } } for(int i=1;i<idx;i++){ for(int j=m;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+v[i]); } } cout<<f[m]; return 0; }

为何要多开数组

#include<bits/stdc++.h> using namespace std; int w,v,c,n,V,l,r,dp[1001],a[1001],b[1001]; void insert(int x,int y,int a,int b) { while(l<=r&&b[r]<=y) r--; r++; a[r]=x; b[r]=y; } int main() { scanf("%d%d",&V,&n); int i,q,d; for(i=1;i<=n;i++) { scanf("%d%d%d",&v,&w,&c); if(!c||V/v<c) c=V/v; for(d=0;d<v;d++) { l=1; r=0; for(q=0;q<=(V-d)/v;q++) { insert(q,dp[qv+d]-qw,a,b); if(a[l]<q-c)l++; dp[qv+d]=b[l]+qw; } } } printf("%d\n",dp[V]); return 0; }