FATE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1914 Accepted Submission(s): 808
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
典型的二维背包,同一维背包差不多,变成2维数组再加多一个循环就行了。至于是01背包还是完全背包还是多重背包看题目意思,怪是无限的,所以是完全背包。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
int c1[105], c2[105], w[105];
int bag[105][105];
int n, V, N, S;
void _td_bag() //二维背包
{
int i, j, k;
memset(bag, 0, sizeof(bag));
for(i = 0; i < N; i++)
{
for(j = c1[i]; j <= V; j++)
{
for(k = c2[i]; k <= S; k++)
{
bag[j][k] = max(bag[j][k], bag[j-c1[i]][k-c2[i]] + w[i]);
}
}
}
}
int main()
{
int i, j;
bool flag;
while(scanf("%d%d%d%d", &n, &V, &N, &S) != EOF)
{
flag = false;
for(i = 0; i < N; i++)
{
//bag[][]代表经验值
scanf("%d %d", &w[i], &c1[i]); //以忍耐度c1[]为容量1
c2[i] = 1; //以怪数量为容量2
}
_td_bag();
for(i = 0; i <= V; i++)
{
if(bag[i][S] >= n) //刚刚升级
{
flag = true;
break;
}
}
if(flag) printf("%d\n", V-i);
else printf("-1\n");
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
2017hdu多校联合训练第一场标程及数据
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
杭电ACMhdu1163
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU2013暑期多校联合训练第一场0723-解题报告和标程
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)