ARC 011 C - 123引き算

問題

問題概要

省略

解法

dpで解いた。dp[i][j] := i回数字を引いて、jになるなら、true、とおいてループで回して埋めていった。 dp[i][j+k]=trueならdp[i][j]=trueとなるので(ただし、jはngでない)、このことから漸化式らしきものが立てられる。

ミス

nがいきなりngである場合が存在するので、注意

コード

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

//dp[i][j] := i回数字を引いて、jになるなら、true
bool dp[110][310];

int ng[3];
bool hantei(int x){
    rep(i, 3){
        if(x == ng[i]) return false;
    }
    return true;
}

int main(void){
    int n; cin >> n;
    rep(i, 3) cin >> ng[i];
    rep(i, 110)rep(j, 310)dp[i][j] = false;

    if(!hantei(n)){//いきなり置けない
        printf("NO\n");
        return 0;
    }

    dp[0][n] = true;
    for (int i = 0; i < 100; ++i){
        for (int j = 0; j <= 300; ++j){
            for (int k = 1; k <= 3; ++k){//引く数
                if(dp[i][j + k] && hantei(j)){
                    dp[i + 1][j] = true;
                }
            }
        }
    }

    for (int i = 0; i <= 100; ++i){
        if(dp[i][0]){
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}