b858: 橘子

沈子耕

內容 ：

吉吉喜歡橘子汁，吉吉有一堆橘子和一台擠汁機，吉吉想用擠汁機擠橘子汁，每顆橘子擠成橘子汁會花不同的時間，擠汁機同時可以擠兩顆橘子，吉吉需要多少時間才能將所有橘子擠成橘子汁。

輸入說明 ：
第 1 行有一正整數 T(T <= 10)，接下來有 T 筆輸入。
每筆輸入 2 行，第 1 行有一正整數 N(N <= 100)，代表橘子數量。下一行有 N 個不超過 1000 的正整數，代表各橘子擠成橘子汁所需要的時間。



有 40% 的測資 N <= 10。

輸出說明 ：
對於每筆輸入，輸出將全部橘子擠成橘子汁所需的最少時間。

範例輸入 ：
2
3
1 2 3
4
1 4 2 3
範例輸出:
3
5
提示 ：
第一筆測資，放入所需時間 1 和 3 的橘子，將所需時間 1 的橘子拿出來，放入所需時間 2 的橘子，全擠成汁需要 3 單位時間。

劉得恩

1. #include<cstdio>
   
2. #include<cstring>
   
3. void print(bool*A,int n)
   
4. {
   
5.     for(int i=0;i<n;i++)
   
6.         printf("%d ",A[i]);
   
7.     puts("");
   
8. }
   
9. int main()
   
10. {
    
11.     bool dp[101000];
    
12.     int t,lemon[105],n;
    
13.     while(scanf("%d",&n)==1)
    
14.     {
    
15.         while(n--)
    
16.         {
    
17.             int sum=0;
    
18.             scanf("%d",&t);
    
19.             for(int i=0; i<t; i++)
    
20.             {
    
21.                 scanf("%d",&lemon[i]);
    
22.                 sum+=lemon[i];
    
23.             }
    
24.             int h=sum/2,dpsum=0;
    
25.             memset(dp,false,sizeof(dp));
    
26.             dp[0]=true;
    
27.             for(int i=0; i<t; i++)
    
28.             {
    
29.                 for(int j=dpsum; j>=0; j--)
    
30.                     if(dp[j])dp[j+lemon[i]]=true;
    
31.                 dpsum+=lemon[i];
    
32.             }
    
33.             //print(dp,sum);
    
34.             int u;
    
35.             for(u=h;; u--)if(dp[u])break;
    
36.             printf("%d\n",sum-u);
    
37.         }
    
38.     }
    
39.     return 0;
    
40. }

複製代碼