返回列表 發帖

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 單位時間。
ABCDEFGHIJKLMNOPQRSTUVWXYZ

  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. }
複製代碼

TOP

返回列表