Board logo

標題: 202409潛力3-天秤Libra [打印本頁]
作者: may    時間: 2024-10-20 15:57     標題: 202409潛力3-天秤Libra

[attach]20106[/attach]
天秤 (Libra)
問題敘述
教室裡有N個砝碼，重量分別為W1, W2. …, WN公克。請判斷是否有可能將砝碼分成兩堆，分別放上天秤的兩端後會呈現出平衡的狀態，也就是兩邊的重量相等。 例如：有N = 3個砝碼，(W1, W2, W3) = (1, 2, 3)。我們分別將重量為W1和W2的砝碼分成一堆、重量為W3的砝碼自己一堆，放上天秤的兩端之後會呈現出平衡狀態，因為兩邊的重量都是3公克。
[attach]20005[/attach]
輸出格式
請輸出一個整數，整數0表示所有的分法皆不可能出現平衡的狀態、整數1則表示可能出現平衡的狀態。
[attach]20006[/attach]
評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (40 分)：N ≤ 20。
第二組 (60 分)：無特別限制。`
https://zerojudge.tw/ShowProblem?problemid=o628
作者: may    時間: 2024-10-20 21:36

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

  4. const int maxn = 100 + 5;

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

  37. int main()
  38. {
  39.         int n;
  40.         int a[maxn];

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

  44.         for (int i = 0; i < n; ++i)
  45.         {
  46.                 scanf("%d", &a[i]);
  47.         }
  48.         printf("%d\n", solve(n, a));

  50.         return 0;
  51. }
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2