//Yukicoder No.4 //重りと天秤 //#include "stdafx.h" #include #include #include #include //list #include //tree #include //連想配列 #include //hash #include //hash #include #include #include #include #include using namespace std; typedef unsigned long long ULL; typedef signed long long SLL; typedef unsigned int UINT; int memo[20000][200]; int N; int W[100]; int _debug_flag = 0; int possible = 0; int _target_weight = 0; // // 半分の重さになるおもりの組み合わせがあるかを調べる // target_weight : おもり // n:おもりのインデックス int func(int n, int target_weight) { //cout << "n=" << n << ",target_weight=" << target_weight << endl; if (possible) return 1; if (n >= N) return 0; if (target_weight > _target_weight) return 0; if (target_weight == _target_weight) { possible = 1; //cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl; return 1; } //同じ引数で関数を通るときは答えは同じなので前回の答えを返す if (-1 != memo[target_weight][n]) { //cout << "memo:n=" << n << ",target_weight=" << target_weight << endl; //cout << "memo ret=" << memo[target_weight][n]<< endl; return memo[target_weight][n]; } _debug_flag |= (1 << n); //最初は n番目のおもりを置いてみる if (func(n + 1, target_weight + W[n])) { //cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl; memo[target_weight][n] = 1; return 1; } _debug_flag &= ~(1 << n); // 上手くいかなかったら n番目のおもりを置かない場合を試してみる if (func(n + 1, target_weight)) { //cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl; memo[target_weight][n] = 1; return 1 ; } //n番目の重りを置いてもおかなくてもだめだった memo[target_weight][n] = 0; return 0; } //降順 int compare(const int * a, const int *b) { if (*a < *b) return (1); else if (*a > *b) return (-1); return (0); } int main() { int total = 0; cin >> N; for (int i=0;i> W[i]; total += W[i]; } if (total % 2) { //そもそも2分割できない合計だったらすぐさまimpossibleを返す cout << "impossible" << endl; return 0; } // 半分に割る _target_weight = total >> 1; //cout << _target_weight << endl; //降順のソート qsort(W, N, sizeof(int), (int(*)(const void*, const void*))compare); memset(memo,-1, 20000*200); //半分の重さになるかを深さ(再帰)探索 if(func(0, 0)) { /* for (int i=0;i