Monkey and Banana HDU - 1069
A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.
The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.
They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.
Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.
InputThe input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.
OutputFor each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height".
Sample Input
1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0
Sample Output
Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342
题意：求解通过垒砖（下面的砖要比上面的砖小，砖的个数不限）可达到的最大高度
由于砖的个数没有规定，题目中只给出了砖的长宽高，每种砖有三种摆法（感觉像是一种砖其实可以当成三块来用）
底面①长*宽②长*高③宽*高，记录的时候用结构体（长宽高底面积）记录比较方便，(￣▽￣)"不要忘了简单按底面积排一下序
dp[i]:用上i块砖的最大高度
在考虑第i块砖时，判断是不是比下面的砖（第j块砖，0<j<i）小（长和宽都要严格小于下面的砖），以此来决定加或者不加
dp[i]=max(dp[j]+block[i].h,dp[i]); //第i块砖可加
#include<iostream> #include<algorithm> #include<string.h> using namespace std; struct blocks { int l, w, h, s; }; bool cmp(blocks &a, blocks &b) { return a.s > b.s; } int t, ll, hh, ww,crt,c=0; blocks b[95]; int dp[95]; void DP() { dp[0] = b[0].h; for (int i = 1; i < crt; i++) { dp[i] = b[i].h; //这里不要忘记 for (int j = 0; j <i; j++) { if ((b[i].l < b[j].l&&b[i].w<b[j].w)||(b[i].l < b[j].w&&b[i].w<b[j].l)) dp[i] = max(dp[i],dp[j] + b[i].h); } } } int main() { while (cin >> t&&t) { c++; crt = 0; blocks bl; while (t--) { cin >> ll >> ww >> hh; bl.l = ll; bl.w = ww; bl.h = hh; bl.s = ll*ww; b[crt++] = bl; bl.l = ll; bl.w = hh; bl.h = ww; bl.s = ll*hh; b[crt++] = bl; bl.l = hh; bl.w = ww; bl.h = ll; bl.s = ww*hh; b[crt++] = bl; } sort(b, b + crt, cmp); DP(); int maxx = 0; for (int i = 0; i < crt; i++) if (maxx < dp[i]) maxx = dp[i]; cout <<"Case "<<c<<": maximum height = " <<maxx << endl; } return 0; }
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!
InputThe 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.
OutputPrint 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
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
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.
题意：给出存钱罐的质量，存钱罐+钱的质量，钱的币值和每种钱的质量，求满足钱的总质量的最大价值
唔……大概差不多也许是个完全背包问题吧
dp[i][j]:用上i种钱质量为j的最大价值
递推：dp[i][j]= max(dp[i][j-w[i]]+v[i],dp[i][j]); j>w[i]
//啊……其实可以直接简化为dp[j]
具体完全背包的分析在这里不再赘述
#include<iostream> #include<algorithm> #include<string> using namespace std; int p[505],w[505]; int t,n,a,b; int dp[10005]; int main() { cin >> t; while (t--) { cin >> a >> b>>n; b -= a; for (int i = 1; i <= n; i++) cin >> p[i] >> w[i]; memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= b; j++) { if (dp[j - w[i]] != 0x3f3f3f3f) { if (dp[j - w[i]] + p[i] < dp[j]) dp[j] = dp[j - w[i]] + p[i]; } } } if (dp[b] != 0x3f3f3f3f) cout << "The minimum amount of money in the piggy-bank is " << dp[b] << "." << endl; else cout << "This is impossible." << endl; } return 0; }