[HDU 1114] Piggy-Bank (动态规划)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114

简单完全背包,不多说。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <map>
 6 #include <iterator>
 7 #include <vector>
 8 using namespace std;
 9 typedef long long LL;
10
11 int T;
12 int E,F;
13 int dp[11111];
14 int p[555],w[555];
15 const int INF = 99999999;
16
17 int main(){
18     scanf("%d",&T);
19     while( T-- ){
20         scanf("%d%d",&E,&F);
21         F -= E;
22         int n;
23         scanf("%d",&n);
24         for(int i=1;i<11111;i++) dp[i] = INF;
25         dp[0] = 0;
26         for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&w[i]);
27         for(int i=1;i<=n;i++){
28             for(int j=w[i];j<=F;j++){
29                 dp[j] = min(dp[j],dp[j-w[i]]+p[i]);
30             }
31         }
32         if( dp[F]!=INF )
33             printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F]);
34         else
35             puts("This is impossible.");
36     }
37     return 0;
38 }
时间: 10-25

[HDU 1114] Piggy-Bank (动态规划)的相关文章

[2016-03-27][HDU][1114][Piggy-Bank]

时间:2016-03-27 16:37:56 星期日 题目编号:[2016-03-27][HDU][1114][Piggy-Bank] 遇到的问题:注意f == e的情况,即dp[0] = 0; #include <cstring> #include <cstdio> #include<algorithm> using namespace std; int dp[10000 + 10]; int w[500 + 10],c[500 + 10]; int main(){

hdu 1114 Piggy-Bank

题目: 链接:点击打开链接 题意: 知道存钱罐的质量和装满硬币的存钱罐的质量,然后是不同硬币的价值和质量,求出存钱罐里钱币的最小价值. 算法: 完全背包问题,银币的个数是不限的. 思路: 状态转移方程:j = 0时,价值为0 dp[j] = min(dp[j],dp[j-w[i]]+v[i]);//表示质量为j的钱币,含有的最小的价值 代码: #include<iostream> #include<cstdio> #include<cstring> using name

[ACM] hdu 1260 Tickets (动态规划)

Tickets Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 4   Accepted Submission(s) : 2 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Jesus, what a great movie! Thou

hdu 1494 跑跑卡丁车(动态规划)

Problem Description 跑跑卡丁车是时下一款流行的网络休闲游戏,你可以在这虚拟的世界里体验驾驶的乐趣.这款游戏的特别之处是你可以通过漂移来获得一种加速卡,用这种加速卡可以在有限的时间里提高你的速度.为了使问题简单化,我们假设一个赛道分为L段,并且给你通过每段赛道的普通耗时Ai和用加速卡的耗时Bi.加速卡的获得机制是:普通行驶的情况下,每通过1段赛道,可以获得20%的能量(N2O).能量集满后获得一个加速卡(同时能量清0).加速卡最多可以储存2个,也就是说当你有2个加速卡而能量再次

hdu 1114 完全背包问题

题意:给定背包体积与物品的体积与价值 求正好放完的最小价值#include<iostream> using namespace std; int min(int a,int b) { if(a<b) return a; return b; } int main() { int t,m1,m2,n,i,j; int v[502],w[502],dp[10005],m; cin>>t; while(t--) { cin>>m1>>m2; m=m2-m1;

HDU 1114 Piggy-Bank(一维背包)

题目地址:HDU 1114 把dp[0]初始化为0,其它的初始化为INF.这样就能保证最后的结果一定是满的,即一定是从0慢慢的加上来的. 代码例如以下: #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #incl

HDU 1114 (dp 完全背包)

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 Problem Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The i

hdu 1114 Piggy-Bank 完全背包

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 题意分析:给出存钱罐存钱前后的重量,以及钱的种类及其价值和种类, 要求装满存钱罐最小的价值.  完全背包 /*Piggy-Bank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13578 Accepted Submission(s):

hdu 4405 Aeroplane chess 动态规划

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4405 所谓概率DP大多是算期望 算期望大多是从终点往回推 简单的1维动态规划 dp[i]表示第i格到终点的期望步数 从终点往前推 若当前为某条捷径的起点 那么该点的dp值直接等于捷径终点的dp值 否则枚举掷出1到6时所到的位置的期望 用最朴素的方法求期望 dp[0]即为所求 #include <cstdio> #include <cstdlib> #include <ctime&