义眼DP

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
int total_sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
total_sum += a[i];
}
int half = total_sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= half; ++j) {
if (j < a[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j - a[i-1]];
}
}
}
int max_sum = 0;
for (int j = half; j >= 0; --j) {
if (dp[n][j]) {
max_sum = j;
break;
}
}
cout << total_sum - 2 * max_sum << endl;
return 0;
}