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
额，这个题有两个包，还有一个good helper，当时不知道怎么写，觉着是dp，然后想出了个二维的方程，复杂度奇高
然后找了下题解才发现可以这样做
只对第一个人dp，如果让第一个人尽量装，然后看剩下的第二个人能不能全部带走，如果可以则Yes
不行则看，如果去除重量最大的一个两个人能不能拿走，可以则Need a helper 否则No
这个helper可以拿任意重的东西，所以如果可能则可以选择把最重的物品给他
我们可以在预处理的时候把最终的放到最后面
f[i][j]表示前i件物品，用j的重量时候能拿走的最大重量
然后这样就是个简单的一维背包了，那么f[n-1][a]则是出去最重一个物品后能取得的最大值
根据背包九讲，我们可以优化空间到一维，但在枚举费用时候要倒序
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