HDU 2639 Bone Collector II 背包k优解-白红宇

HDU 2639 Bone Collector II 背包k优解

阅读量：5265 次

发布时间：2019-06-14

本文共 785 字，大约阅读时间需要 2 分钟。

01背包的转移方程为

dp[j]=max(dp[j],dp[j-vol[i]+cost[i]]);

因为要求解第k大的解

需要用二位数组储存

即dp[j][k];

j为体积 k为第几优的解

所以保存下转移过程中dp[j]与dp[j-vol[i]]的前k大的值

dp[j]与dp[j-vol[i]]两个状态中一共有k*2个值取其中前k大的数赋值与dp[j]中；

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            
             #include 
             
              using namespace std;#define MAXN 100*111#include 
              
               #include 
               
                #define IN freopen("in.txt","r",stdin);int dp[1111][33],a[101],b[101],ans[333];bool cmp(int a,int b){ return a>b;}int main(){ int n,t,v,k; // IN; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&v,&k); memset(dp,0,sizeof(dp)); for(int i=0; i
                
                 =b[i]; j--) { tot=0; memset(ans,0,sizeof(ans)); for(int p=0;p