链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70533#overview
A - poj1837
Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u
Description
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25.
Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.
Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.
Input
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis
(when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the
hook is attached: '-' for the left arm and '+' for the right arm);
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.
Output
Sample Input
2 4 -2 3 3 4 5 8
Sample Output
2
这题要理解题意,意思是有n个 挂钩,m个砝码,要求挂上所有的砝码,使得左右两边平衡,对于左右两端的正负,我们可以全部正数化。
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> using namespace std; #define N 30 int a[N]; int b[N]; int dp[N][15100];// 放置i个砝码,使得值为j 的方法数,正数化之后,去最后的dp[n][7500]. int main() { int n, m; while(~scanf("%d%d",&n,&m)) { for(int i = 1; i <= n; i ++) { scanf("%d",&a[i]); } for(int j = 1; j <= m; j ++) { scanf("%d",&b[j]); } dp[0][7500] = 1; for(int i = 1; i <= m; i ++) { for(int k = 1; k <= n; k ++) { for(int j = a[k]*b[i] ; j <= 15000; j ++) { int tmp_1 = dp[i - 1][j - a[k]*b[i]]; if(tmp_1 > 0) { dp[i][j] += tmp_1; } } } } printf("%d\n", dp[m][7500]); } return 0; }
B - poj1276
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d
& %I64u
Description
of nk bills. For example,
N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10
means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.
Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.
Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input
cash N n1 D1 n2 D2 ... nN DN
where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers
in the input. The input data are correct.
Output
Sample Input
735 3 4 125 6 5 3 350 633 4 500 30 6 100 1 5 0 1 735 0 0 3 10 100 10 50 10 10
Sample Output
735 630 0 0
Hint
In the second case the bill supply of the machine does not fit the exact amount of cash requested. The maximum cash that can be delivered is @630. Notice that there can be several possibilities to combine the bills in the machine for matching the delivered
cash.
In the third case the machine is empty and no cash is delivered. In the fourth case the amount of cash requested is @0 and, therefore, the machine delivers no cash.
简单的多重背包
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> using namespace std; #define N 100010 int dp[N]; int c[N]; int cash, n; int main() { int sum, price; while(~scanf("%d%d",&cash,&n)) { int cnt = 1; for(int i = 0; i < n; i ++) { scanf("%d%d",&sum,&price); int t = 1; while(sum >= t) { c[cnt ++] = t * price; sum = sum - t; t = t << 1; } if(sum) { c[cnt ++] = sum * price; } } if(cash == 0 || n == 0) { printf("0\n"); continue; } memset(dp, 0, sizeof(dp)); for(int i = 1; i < cnt; i ++) { for(int j = cash; j >= c[i]; j --) { dp[j] = max(dp[j], dp[j - c[i]] + c[i]); } } printf("%d\n", dp[cash]); } }
F - poj2533
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d
& %I64u
Description
be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence
(1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
Output
Sample Input
7 1 7 3 5 9 4 8
Sample Output
4
最长上升子序列,模版题
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define N 1010 int tt[N]; int slen[N]; void init(int n) { for(int i = 1; i <= n; i ++) { slen[i] = 1; } } int main() { int n; while(~scanf("%d",&n)) { init(n); for(int i = 1; i <= n; i ++) { scanf("%d",&tt[i]); } int ans = 1; for(int i = 2; i <= n; i ++) { int maxn = 0; for(int j = 1; j <= i - 1; j ++) { if(tt[j] < tt[i] && slen[j] > maxn) maxn = slen[j]; } slen[i] = maxn + 1; if(slen[i] > ans) ans = slen[i]; } printf("%d\n",ans); } }
G - poj3176
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d
& %I64u
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest
score wins that frame.
Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.
Input
Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.
Output
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
Hint
7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5
The highest score is achievable by traversing the cows as shown above.
这题就是数塔问题,一般都是入门DP 的第一道题吧, 我也只会这个、、、 - -b
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> using namespace std; #define N 400 int tt[N][N]; int main() { int n; while(~scanf("%d",&n)) { memset(tt, 0, sizeof(tt)); for(int i = 1; i <= n; i ++) { for(int j = 1; j <= i; j ++) { scanf("%d",&tt[i][j]); } } for(int i = n; i >= 1; i --) { for(int j = i; j >= 1; j --) { tt[i][j] += max(tt[i + 1][j], tt[i + 1][j + 1]); } } printf("%d\n", tt[1][1]); } }
I - poj1159
Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d
& %I64u
Description
to obtain a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Input
from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.
Output
Sample Input
5 Ab3bd
Sample Output
2
其实就是lcs,求出lcs之后,答案就为n - lcs,但是这里需要动态数组的优化,不然内存会不够
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define N 5005 int dp[2][N]; char s1[N]; char s2[N]; int main() { int n; while(~scanf("%d",&n)) { scanf("%s",s1); for(int i = 0; i < n; i ++) { s2[i] = s1[n - i - 1]; } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { if(s1[i - 1] == s2[j - 1]) { dp[i%2][j] = dp[(i - 1)%2][j - 1] + 1; } else dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]); } } printf("%d\n", n - dp[n%2][n]); } }