相当于在背包上面挂vector，这样我们就可以求出容量为j所有k优解

转移是把dp[i-1][j][k] 和 dp[i-1][j-w[i]][k]向dp[i][j][k]上转移，因为这两个地方的k优解的2k个解里一定含有dp[i][j]的k优解，而且这两个序列有单调性

可以直接把所有数赋为-inf然后如果不满足从0开始装更新到最后也是负数，最后判断dp[n][m][k]是否是负数就可以了

然后滚动数组

1 /* 2 ID: ivorysi 3 LANG: C++ 4 TASK: theme 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 #include 
           
            13 #include 
            
             14 #define siji(i,x,y) for(int i=(x);i<=(y);++i)15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)18 #define inf 0x7fffffff19 #define ivorysi20 #define mo 9779797721 #define hash 97471122 #define base 4723 #define pss pair
             
              24 #define MAXN 500025 #define fi first26 #define se second27 #define pii pair
              
               28 typedef long long ll;29 using namespace std;30 int n,m,k;31 int w[205],c[205];32 int dp[5005][55];33 int line[55],ans;34 void solve() {35 scanf("%d%d%d",&k,&m,&n);36 siji(i,1,n) scanf("%d%d",&w[i],&c[i]);37 siji(j,0,m) siji(i,1,k) dp[j][i]=-4000000;38 dp[0][1]=0;39 siji(i,1,n) {40 gongzi(j,m,w[i]) {41 int t1=1,t2=1;42 siji(h,1,k) {43 if(dp[j-w[i]][t1]+c[i] > dp[j][t2]) {44 line[h]=dp[j-w[i]][t1]+c[i];45 ++t1;46 }47 else {48 line[h]=dp[j][t2];49 ++t2;50 }51 }52 siji(h,1,k) dp[j][h]=line[h];53 }54 }55 if(dp[m][k] < 0) {puts("no");return;}56 siji(i,1,k) {57 ans+=dp[m][i];58 }59 printf("%d\n",ans);60 } 61 int main(int argc, char const *argv[])62 {63 #ifdef ivorysi64 freopen("24.in","r",stdin);65 freopen("24.out","w",stdout);66 #else67 freopen("f1.in","r",stdin);68 #endif69 solve();70 return 0;71 }