当前位置:编程学习 > C/C++ >>

HDU 2159 FATE

思路:二维背包
 
将经验看作价值有动态转移:dp[ i ][ j ]=max(dp[ i ][ j ],dp[ i-r[ k ] ][ j-1 ]+v[ k ])  .

v[k]表示杀第k种怪一只所得的经验,将耗去r[k]忍耐度。

[cpp] 
#include<stdio.h> 
#include<string.h> 
#define max(a,b) (a)>(b)?(a):(b) 
int dp[101][101]; 
int v[101],r[101]; 
int main() 

   int n,m,k,s,i,j,l; 
   while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) 
   { 
       for(i=0;i<k;i++) 
          scanf("%d%d",&v[i],&r[i]); 
          memset(dp,0,sizeof(dp)); 
          for(i=0;i<k;i++) 
             for(j=r[i];j<=m;j++) 
                 for(l=1;l<=s;l++) 
                    dp[j][l]=max(dp[j][l],dp[j-r[i]][l-1]+v[i]); 
        int flag=0; 
        for(i=0;i<=m;i++)//遍历满足的经验的最小消耗忍耐度 
        { 
            if(flag) break; 
            for(j=1;j<=s;j++)//怪的数量限制 
            { 
                if(dp[i][j]>=n)  
                { 
                    j=i;flag=1;break; 
                } 
            } 
        } 
        if(!flag) printf("-1\n"); 
        else printf("%d\n",m-j); 
                
   } 
   return 0; 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,