返回列表 發帖

202409潛力3-天秤Libra


天秤 (Libra)
問題敘述
教室裡有N個砝碼,重量分別為W1, W2. …, WN公克。請判斷是否有可能將砝碼分成兩堆,分別放上天秤的兩端後會呈現出平衡的狀態,也就是兩邊的重量相等。 例如:有N = 3個砝碼,(W1, W2, W3) = (1, 2, 3)。我們分別將重量為W1和W2的砝碼分成一堆、重量為W3的砝碼自己一堆,放上天秤的兩端之後會呈現出平衡狀態,因為兩邊的重量都是3公克。

輸出格式
請輸出一個整數,整數0表示所有的分法皆不可能出現平衡的狀態、整數1則表示可能出現平衡的狀態。

評分說明
此題目測資分成兩組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該組分數,各組詳細限制如下。
第一組 (40 分):N ≤ 20。
第二組 (60 分):無特別限制。`
https://zerojudge.tw/ShowProblem?problemid=o628
附件: 您需要登錄才可以下載或查看附件。沒有帳號?註冊
May

  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. const int maxn = 100 + 5;

  4. int solve(int n, int *a)
  5. {
  6.         int *dp = nullptr;
  7.         int sum = 0;
  8.         int ret = 0;
  9.         for (int i = 0; i < n; i++)
  10.         {
  11.                 sum += a[i];
  12.         }
  13.         if (sum % 2)
  14.         {
  15.                 return 0;
  16.         }
  17.         dp = new int[sum + 1];
  18.         memset(dp, 0, sizeof(int) * (sum + 1));
  19.         dp[0] = 1;
  20.         for (int i = 0; i < n; i++)
  21.         {
  22.                 for (int j = sum; j >= a[i]; j--)
  23.                 {
  24.                         if (dp[j - a[i]])
  25.                         {
  26.                                 dp[j] = 1;
  27.                         }
  28.                 }
  29.         }
  30.         ret = dp[sum / 2];
  31.         delete [] dp;
  32.         return ret;
  33. }

  34. int main()
  35. {
  36.         int n;
  37.         int a[maxn];

  38.         scanf("%d", &n);

  39.         for (int i = 0; i < n; ++i)
  40.         {
  41.                 scanf("%d", &a[i]);
  42.         }
  43.         printf("%d\n", solve(n, a));

  44.         return 0;
  45. }
複製代碼
May

TOP

返回列表