P1013 （C++代码）

解题思路:





注意事项:





参考代码:

双重状态数组，我无敌了。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 2020
using namespace std;
int n,ti[maxn],sum_tot,f[maxn][maxn],rmb[maxn],m,rp[maxn],r,sum[maxn][maxn];
int read()//读入优化，背过即可 
{    
int x=0;   
 char ch=getchar();    
 while(ch<'0'||ch>'9') ch=getchar();   
  while(ch>='0'&&ch<='9')     
  {         
  x=x*10+ch-'0';         
  ch=getchar();     
  }    
  return x;}
int main()
{    
n=read();    
for(int i=1;i<=n;++i)     
{         rmb[i]=read();         
rp[i]=read();         
ti[i]=read();
//应该都是题目给的变量，不过time改成ti，貌似time是个特殊玩意==      
}    m=read();r=read();   
 //差不多就是个01背包，然后j,v就这么出来，比普通的多了一层     
 for(int i=1;i<=n;++i)     for(int j=r;j>=rp[i];--j)      
 for(int v=m;v>=rmb[i];--v)       
 {           
 if(sum[j][v]<sum[j-rp[i]][v-rmb[i]]+1)            
 {                
 sum[j][v]=sum[j-rp[i]][v-rmb[i]]+1;//sum数组代表泡到最多mm                 
 f[j][v]=f[j-rp[i]][v-rmb[i]]+ti[i];//更新泡到最多mm时的花费时间           
   }        if(sum[j][v]==sum[j-rp[i]][v-rmb[i]]+1)         
   {             f[j][v]=min(f[j][v],f[j-rp[i]][v-rmb[i]]+ti[i]);            
    //如果已经泡到了目前阶段最多的mm，则更新一下最少的时间         
     }      
      }   
       printf("%d\n",f[r][m]);//想一想，普通01背包的f后面（成员）不是也跟着个最大值吗   
         return 0;}
一定要点赞！！！！！！！！！