202409潛力3-天秤Libra

may

天秤 (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. 
   
4. const int maxn = 100 + 5;
   
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. }
    
36. 
    
37. int main()
    
38. {
    
39.         int n;
    
40.         int a[maxn];
    
41. 
    
42.         scanf("%d", &n);
    
43. 
    
44.         for (int i = 0; i < n; ++i)
    
45.         {
    
46.                 scanf("%d", &a[i]);
    
47.         }
    
48.         printf("%d\n", solve(n, a));
    
49. 
    
50.         return 0;
    
51. }

複製代碼