FATE
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3051Accepted Submission(s): 1297
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 101 110 10 1 91 19 10 2 101 12 2
Sample Output
Author
Xhd
二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代
价都有 一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2
,第i件物品所需的两种代价分别为a[i]和 b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值
为w[i]。
费用加了一维,只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。
状态转移方程就是:
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量v和u采用逆序的循环,当物品有如完全背包问题
时采用顺序的循环。当物品有如多重背包问题时拆分物品。
for(i = 1; i <= M; i++)
{
for(j = 1; j <= S; j++)
for(k = 1; k <= K; k++) if(i - b[k] >= 0)
{
if(d[i - b[k]][j - 1] + a[k] >= d[i][j])
d[i][j] = d[i - b[k]][j - 1] + a[k];
}
if (d[i][S] >= N) break;
}
一开始一点思路都木有 哎 还是参考了人家的代码
啥时候能自己搞定啊
3个循环层的排放顺序无关紧要 怎么放 谁在内谁在外都可以
另外记住是求所有满足升级情况下的 剩余最大值
一开始我求的只是满足的值 没求最大值 WA了 接近10次啊
那叫一个难受啊
#include<stdio.h>
#include<string.h>
int n,m,k,s;
int jingyan[105],rennai[105],bag[105][105];
int _bag()
{
int i,j,t,jieguo=-1;
memset(bag,0,sizeof(bag));
for(i=0;i<k;i++)
for(t=1;t<=s;t++)
for(j=rennai[i];j<=m;j++)
{
if(bag[j][t]<bag[j-rennai[i]][t-1]+jingyan[i])
bag[j][t]=bag[j-rennai[i]][t-1]+jingyan[i];
if(bag[j][t]>=n) jieguo=m-j>jieguo?m-j:jieguo;
}
return jieguo;
}
int main()
{
int i,j;
while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF)
{
for(i=0;i<k;i++)
scanf("%d %d",&jingyan[i],&rennai[i]);
printf("%d\n",_bag());
}
}
相关推荐
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧