HDU 1248 寒冰王座(全然背包:入门题)
http://acm.hdu.edu.cn/showproblem.php?pid=1248
题意:
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,仅仅有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,可是要尽量少让他赚小费.
如今死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
分析:
仅仅有3种商品, 且无限供应, 明显的全然背包问题.
本题限制条件: 总费用<=N
本题目标条件: 总费用尽量大.
令dp[i][j]==x 表示仅仅购买前i种商品时, 总花费<=j元时, 最多能花x元钱.
初始化: dp全为0.
状态转移: dp[i][j] = max( dp[i-1][j] , dp[i][j-val[i]]+val[i])
前者表示第i种商品一个都不买, 后者表示至少买1个第i种商品.
终于所求: dp[n][N]. n为商品数,本题n==3. N为初始金钱数目. 可是我们要输出 N-dp[n][N].
程序实现用的滚动数组, 所以dp仅仅有[j]一维.
AC代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=10000+5; int n=3; int val[]={150,200,350};//每种商品价格 int dp[maxn]; int main() { //初始化 memset(dp,0,sizeof(dp)); //递推 for(int i=0;i<n;i++) { for(int j=val[i];j<maxn;j++) dp[j] = max(dp[j], dp[j-val[i]]+val[i]); } //处理每一个输入实例 int T; scanf("%d",&T); while(T--) { int x; scanf("%d",&x); printf("%d\n",x-dp[x]); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/4095441.html
相关资源：各显卡算力对照表！