(ΦωΦ)<これの答えですよー。目次はここ。
---
問1-1
#include <iostream>
#include <algorithm>
using namespace std;
int n;
vector<int> w;
vector<vector<int>> dp;
int half;
// i番目を左に置こうか右に置こうか迷っている状態。
// これまでの左の重さはweight。
bool rec(int i, int weight) {
if(dp[i][weight] != -1) { return dp[i][weight]; }
if(i == n) { return weight==half; }
return
dp[i][weight] = rec(i+1, weight+w[i]) ||
rec(i+1, weight);
}
int main(void) {
scanf("%d", &n);
w.assign(n, 0);
int summa = 0;
for(int i=0; i<n; i++) {
scanf("%d", &w[i]);
summa += w[i];
}
if(summa & 1) {
puts("impossible");
return 0;
}
dp.assign(n+1, vector<int>(summa+1, -1));
half = summa / 2;
puts(rec(0, 0) ? "possible" : "impossible");
return 0;
}
(ΦωΦ)<おしまい