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