【端午小练】HDU2159-FATE-阿里云开发者社区

开发者社区> 开发与运维> 正文

【端午小练】HDU2159-FATE

简介:

FATE
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7141    Accepted Submission(s): 3289


Problem Description
最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀

怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应

的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗?
 

Input
输入数据有多组,对于每组数据第一行输入n,m,k,s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值,保留的忍耐度,怪的种数和

最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a,b(0 < a,b < 20);分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的

忍耐度。(每种怪都有无数个)
 

Output
输出升完这级还能保留的最大忍耐度,如果无法升完这级输出-1。
 

Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
 

Sample Output
0
-1
1
 

Author
Xhd
 

Source
2008信息工程学院集训队——选拔赛

 


完全背包+状态次数记录
AC代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
   int M,L;   //M是杀一只怪给的经验,L是杀死怪物后减去的忍耐值   
}per[110];
int cmp(node x,node y)
{
    if(x.M!=y.M) return x.M>y.M;
    if(x.L!=y.L) return x.L<y.L;
}
int dp[110];
int main()
{
    int i,j,n,m,k,s,count[110];
    while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF)
    {
       for(i=0;i<k;i++)
       scanf("%d %d",&per[i].M,&per[i].L);
       sort(per,per+k,cmp);
       memset(dp,0,sizeof(dp));
       memset(count,0,sizeof(count));
       for(i=0;i<k;i++)
       for(j=per[i].L;j<=m;j++)
       {
          if(dp[j]<dp[j-per[i].L]+per[i].M)//取经验最多的情况,减去本次情况的忍耐度
          {
             dp[j]=dp[j-per[i].L]+per[i].M;
             count[j]=count[j-1]+1;//记录每个忍耐度的情况下的杀怪数 
          }
       }
       int flag=0;
       for(i=1;i<=m;i++)
       {
          if(dp[i]>=n&&count[i]<=s)
          {
              printf("%d\n",m-i);
              flag=1;
              break;
          }
       }
       if(flag==0)
       printf("-1\n");
    }
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章