网页链接：传送门
密码：hpuacm

A - Bone Collector (HDU-2602)

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T, the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 2³¹).

Sample Input	Sample Output
1 5 10 1 2 3 4 5 5 4 3 2 1	14

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=5010;int T,N,V,v[maxn],w[maxn],f[maxn];int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&N,&V);for(int i=1;i<=N;i++)	//价值 scanf("%d",&v[i]);for(int i=1;i<=N;i++)scanf("%d",&w[i]);	//体积 memset(f,0,sizeof(f));for(int i=1;i<=N;i++){for(int j=V;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+v[i]);}}printf("%d\n",f[V]);}return 0;
}

---

B - 饭卡 (HDU-2546)

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample Input	Sample Output
1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0	-45 32

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=1010;int N,M,v[maxn],f[maxn];int main()
{while(~scanf("%d",&N)){if(N==0)	break;for(int i=1;i<=N;i++)	//价格 scanf("%d",&v[i]);sort(v+1,v+1+N);scanf("%d",&M);memset(f,0,sizeof(f));if(M>=5){for(int i=1;i<=N-1;i++){for(int j=M-5;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+v[i]);}}printf("%d\n",M-f[M-5]-v[N]);}elseprintf("%d\n",M);}return 0;
}

---

C - Robberies (HDU-2955)

The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
Input
The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
Output
For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.

Sample Input	Sample Output
3 0.04 3 1 0.02 2 0.03 3 0.05 0.06 3 2 0.03 2 0.03 3 0.05 0.10 3 1 0.03 2 0.02 3 0.05	2 4 6

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=11000;int T,N,m[maxn/100],sum;
double P,p[maxn/100],f[maxn];int main()
{scanf("%d",&T);while(T--){scanf("%lf%d",&P,&N);sum=0;P=1-P;	//不被抓概率 for(int i=1;i<=N;i++){scanf("%d%lf",&m[i],&p[i]);	//价值  被抓概率 sum+=m[i];	//总价值 p[i]=1-p[i];	//不被抓概率 }memset(f,0,sizeof(f));f[0]=1.0;for(int i=1;i<=N;i++){for(int j=sum;j>=m[i];j--){f[j]=max(f[j],f[j-m[i]]*p[i]);}}for(int i=sum;i>=0;i--){if(f[i]>=P){printf("%d\n",i);break;}}}return 0;
}

---

D - Piggy-Bank (HDU-1114)

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 idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it’s weight in grams.
Output
Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”.

Sample Input	Sample Output
3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4	The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=11000;
const ll INF=0x3f3f3f3f;int T,E,F,N,V,p[maxn/20],w[maxn/20],f[maxn];int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&E,&F,&N);V=F-E;for(int i=1;i<=N;i++)scanf("%d%d",&p[i],&w[i]);	//价值    重量 memset(f,INF,sizeof(f));f[0]=0;for(int i=1;i<=N;i++){for(int j=w[i];j<=V;j++){f[j]=min(f[j],f[j-w[i]]+p[i]);}}if(f[V]==INF)	printf("This is impossible.\n");else{printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]);}}return 0;
}

---

E - 钱币兑换问题 (HDU-1284)

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。

Sample Input	Sample Output
2934 12553	718831 13137761

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=40000;ll N,f[maxn];int main()
{while(~scanf("%lld",&N)){memset(f,0,sizeof(f));f[0]=1;for(int i=1;i<=3;i++){for(int j=i;j<=N;j++){f[j]+=f[j-i];}}printf("%lld\n",f[N]);}return 0;
}

---

F - 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 (HDU-2191)

急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？
后记：
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
感谢父母，他们给予我们生命，抚养我们成人；
感谢老师，他们授给我们知识，教我们做人
感谢朋友，他们让我们感受到世界的温暖；
感谢对手，他们令我们不断进取、努力。
同样，我们也要感谢痛苦与艰辛带给我们的财富～
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

Sample Input	Sample Output
1 8 2 2 100 4 4 100 2	400

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=210;int T,N,M,p[maxn],h[maxn],c[maxn],f[maxn];int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&N,&M);for(int i=1;i<=M;i++){scanf("%d%d%d",&p[i],&h[i],&c[i]);}memset(f,0,sizeof(f));for(int i=1;i<=M;i++){int num=c[i];for(int k=1;num>0;k<<=1){int mul=min(k,num);for(int j=N;j>=p[i]*mul;j--){f[j]=max(f[j],f[j-p[i]*mul]+h[i]*mul);}num-=mul;}}printf("%d\n",f[N]);}return 0;
}

---

G - CD (UVA 624)

You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
● number of tracks on the CD. does not exceed 20
● no track is longer than N minutes
● tracks do not repeat
● length of each track is expressed as an integer number
● N is also integer
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Input
Any number of lines. Each one contains value N, (after space) number of tracks and durations of the tracks. For example from first line in sample data: N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes
Output
Set of tracks (and durations) which are the correct solutions and string “sum:” and sum of duration times.

Sample Input	Sample Output
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2	1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45

1. 第一种方法

   #include<cstdio>
   #include<algorithm>
   #include<cstring>
   using namespace std;
   typedef long long ll;
   const ll maxn=5010;int V,N,v[maxn],f[maxn];
   bool bj[25][maxn];int main()
   {while(~scanf("%d%d",&V,&N)){for(int i=1;i<=N;i++)scanf("%d",&v[i]);memset(f,0,sizeof(f));memset(bj,false,sizeof(bj));for(int i=1;i<=N;i++){for(int j=V;j>=v[i];j--){if(f[j]<f[j-v[i]]+v[i]){f[j]=f[j-v[i]]+v[i];bj[i][j]=true;}}}for(int i=N,j=V;i>=0;i--){if(bj[i][j]){printf("%d ",v[i]);j-=v[i];}}printf("sum:%d\n",f[V]);}return 0;
   }
   

2. 第二种方法

   #include<cstdio>
   #include<cstring>
   using namespace std;
   typedef long long ll;
   const ll maxn=5010;int V,N,v[maxn],w[maxn],f[maxn];void dfs(int x)	//递归路径   x 是状态值   w[x] 是上一个状态到该状态的增值   x - w[x]  是上一个状态 
   {if(f[x]==0)		//到起点就返回 return;dfs(f[x-w[x]]);	//找上一个点 printf("%d ",w[x]);	//输出这个点 
   }int main()
   {while(~scanf("%d%d",&V,&N)){	for(int i=1;i<=N;i++)scanf("%d",&v[i]);memset(f,0,sizeof(f));memset(w,0,sizeof(w));for(int i=1;i<=N;i++){for(int j=V;j>=v[i];j--){if(f[j]<f[j-v[i]]+v[i]){f[j]=f[j-v[i]]+v[i];	//更新最优解 w[j]=v[i];	//记录下我们在这个点增加的值 }}}dfs(f[V]);	//输出路径 printf("sum:%d\n",f[V]);}return 0;
   }
   

3. 第三种方法

   #include<cstdio>
   #include<vector>
   #include<cstring>
   using namespace std;
   typedef long long ll;
   const ll maxn=5010;
   const ll INF=0x3f3f3f3f;int V,N,v[25],f[maxn];
   vector<int> ve[maxn];int main()
   {while(~scanf("%d%d",&V,&N)){for(int i=1;i<=N;i++)scanf("%d",&v[i]);memset(f,INF,sizeof(f));f[0]=1;for(int i=1;i<=N;i++){for(int j=V;j>=v[i];j--){if(f[j-v[i]]<f[j]){f[j]=1;ve[j]=ve[j-v[i]];ve[j].push_back(i);}//			else if((f[j-v[i]]==1) && f[j-v[i]]==f[j])//			{//				int len=ve[j-v[i]].size()+1;//				if(len>ve[j].size())//				{//					ve[j]=ve[j-v[i]];//					ve[j].push_back(i);//				}//			}}}for(int i=V;i>=0;i--){if(f[i]==1){for(int j:ve[i]){printf("%d ",v[j]);}printf("sum:%d\n",i);break;}}}
   }