読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.4 おもりと天秤

問題

問題概要

省略。

解法

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