標題:
202409潛力3-天秤Libra
[打印本頁]
作者:
may
時間:
2024-10-20 15:57
標題:
202409潛力3-天秤Libra
[attach]20106[/attach]
天秤 (Libra)
問題敘述
教室裡有N個砝碼,重量分別為W
1
, W
2
. …, W
N
公克。請判斷是否有可能將砝碼分成兩堆,分別放上天秤的兩端後會呈現出平衡的狀態,也就是兩邊的重量相等。 例如:有N = 3個砝碼,(W
1
, W
2
, W
3
) = (1, 2, 3)。我們分別將重量為W
1
和W
2
的砝碼分成一堆、重量為W
3
的砝碼自己一堆,放上天秤的兩端之後會呈現出平衡狀態,因為兩邊的重量都是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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
int solve(int n, int *a)
{
int *dp = nullptr;
int sum = 0;
int ret = 0;
for (int i = 0; i < n; i++)
{
sum += a[i];
}
if (sum % 2)
{
return 0;
}
dp = new int[sum + 1];
memset(dp, 0, sizeof(int) * (sum + 1));
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = sum; j >= a[i]; j--)
{
if (dp[j - a[i]])
{
dp[j] = 1;
}
}
}
ret = dp[sum / 2];
delete [] dp;
return ret;
}
int main()
{
int n;
int a[maxn];
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
printf("%d\n", solve(n, a));
return 0;
}
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2