yukicoder No.4 おもりと天秤 問題の言い換え
yukicoder No.4 おもりと天秤
問題概要
リンク参照
考察
- 天秤が釣り合う→重さの総和の半分の重さが作ることができればpossibleになる
- dp[i]:=重さiを作れるか(作れる場合は1)とし,dp[0]=1で初期化
- dp[i]==1の場合はdp[i+W[i]]=1と遷移できる(配列外参照に注意)
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; /******************************************************************************************/ int dp[10005]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> W(N); int sum = 0; for (int i = 0; i < N; i++) { cin >> W[i]; sum += W[i]; } dp[0] = 1; if (sum % 2) { cout << "impossible" << endl; return 0; } for (int i = 0; i < N; i++) { for (int j = 10000; j >= 0; j--) { if (dp[j] == 0)continue; if (j + W[i] <= 10000) { dp[j + W[i]] = 1; } } } if (dp[sum / 2] == 1) { cout << "possible" << endl; } else { cout << "impossible" << endl; } }