A Good Helper
| Source : HCPC 2004 |
| Time limit : 1 sec |
| Memory limit : 32 M |
Submitted : 476, Accepted : 205
Abraham and Calford are Moving their things from dormitory A11 to A9,and they have their own carry limit,they can't carry things which is beyond their limit and they will not carry one bag together. They want things to be carried in one time,when they can't deal with so many things, they will hire a good helper to help them, who can only carry one bag of things, regardless of the weight of it. Your task is to tell whether they can carry their bags in one time,or not.
Input
There are multiple test cases.
First line of each test case contains two nonnegative numbers, A and C, (0 < A,C <=1000) representing the limit of Abraham and Calford,then the second line contains an integer N ( 0 < N <= 200 ) ,representing the number of bags,followed by N positive integers,each of them is not more than 100.
Output
For each test case
Output "Yes" if they can carry the bags without the help of the helper in one time.
Output "Need a helper" if they can only carry the bags with the help of the helper in one time.
Output "No" if they can't carry the bags in one time.
Sample Input
7 7
3 5 5 5
7 7
3 5 2 5
7 7
3 7 8 7
7 7
3 7 8 9
Sample Output
Need a helper
Yes
Need a helper
No
額，這個(gè)題有兩個(gè)包，還有一個(gè)good helper，當(dāng)時(shí)不知道怎么寫(xiě)，覺(jué)著是dp，然后想出了個(gè)二維的方程，復(fù)雜度奇高
然后找了下題解才發(fā)現(xiàn)可以這樣做
只對(duì)第一個(gè)人dp，如果讓第一個(gè)人盡量裝，然后看剩下的第二個(gè)人能不能全部帶走，如果可以則Yes
不行則看，如果去除重量最大的一個(gè)兩個(gè)人能不能拿走，可以則Need a helper 否則No
這個(gè)helper可以拿任意重的東西，所以如果可能則可以選擇把最重的物品給他
我們可以在預(yù)處理的時(shí)候把最終的放到最后面
f[i][j]表示前i件物品，用j的重量時(shí)候能拿走的最大重量
然后這樣就是個(gè)簡(jiǎn)單的一維背包了，那么f[n-1][a]則是出去最重一個(gè)物品后能取得的最大值
根據(jù)背包九講，我們可以優(yōu)化空間到一維，但在枚舉費(fèi)用時(shí)候要倒序
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 int f[1300],a,c;
5 int n,v[240];
6 int big,tmp,xi;
7 int tot;
8 void init()
9 {
10 int i,temp;
11 scanf("%d",&n);
12 big=0;
13 tot=0;
14 for(i=1;i<=n;i++)
15 {
16 scanf("%d",&v[i]);
17 tot+=v[i];
18 if (v[i]>big)
19 {
20 big=v[i];
21 xi=i;
22 }
23 }
24 temp=v[xi];v[xi]=v[n];v[n]=temp;
25 }
26 int max(int a,int b)
27 {
28 if (a>b) return a; else return b;
29 }
30 void work()
31 {
32 int i,j;
33 memset(f,0,sizeof(f));
34 for (i=1;i<=n ;i++ )
35 {
36 for (j=a;j>=v[i] ;j-- )
37 {
38 tmp=f[a];
39 f[j]=max(f[j-v[i]]+v[i],f[j]);
40 }
41 }
42 if (f[a]+c>=tot) printf("Yes\n");
43 else if (tmp+c>=tot-big) printf("Need a helper\n");
44 else printf("No\n");
45 }
46 int main()
47 {
48 while (scanf("%d%d",&a,&c)!=EOF)
49 {
50 init();
51 work();
52 }
53 return 0;
54 }
55