yukicoder No.4 おもりと天秤

問題

問題概要

省略。

解法

dp[i番目までのおもりを見た時][左側の重さj] := (trueならある)というbool型の配列を用意して、i番目のおもりの時に、左側の重さがjが存在するかをdpで探索していく。単純におもりが左の天秤なのか右の天秤なのかでやってしまうと計算量がＯ(2^N)となってしまうN=100のときなどは無理になってしまう。しかし動的計画法を使うことで、計算量がＯ(10000*n)となり、ACが取れる。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i番目までのおもりを見た時][左側の重さ] := (trueならある)
bool dp[101][10001];
int main(void){
    rep(i, 101)rep(j, 10001) dp[i][j] = false;
    int n; cin >> n;
    vector<int> w(n);
    rep(i, n)cin >> w[i];

    int sum = 0;
    rep(i, n) sum += w[i];
    if(sum % 2 == 1){
        printf("impossible\n");
        return 0;
    }

    dp[0][0] = true;
    for (int i = 0; i < n ; ++i){
        for (int j = 0; j <= 10000; ++j){
            if(dp[i][j] == true){
                //左側の天秤に入れる
                dp[i + 1][j + w[i]] = true;
                //右側の天秤に入れる
                dp[i + 1][j] = true;
            }
        }
    }

    if(dp[n][sum / 2] == true) printf("possible\n");
    else printf("impossible\n");
    return 0;
}