ABC153 E-Crested Ibis VS Monste - 草体にぼ日記

ABC153 E-Crested Ibis VS Monster

[DP Dynamic Proggramming, 動的計画法] DPっぽいよなあ。って問題。解説動画によると、二次元DPでも一次元DPでも行けるとのこと。とりあえず頑張って二次元で書けと言われたので書いた。 2次元dpでの提出コード提出コード

さらにこれをちょっと見て、一次元dpを書いた。提出コード1次元DP

コードの説明をすると、とっても嬉しいのでコードの説明をしていこうか。

まずは二次元DPから

愛も変わらず#includeなどグローバルな部分はカットします。全部見たい方は上のリンクを覗いてください

int main()
{
    //入力
    ll h , n ;
    cin >> h >> n ;
    vector<pair<ll,ll>> p(n);//攻撃力、消費MP
    rep(i,n) cin >> p[i].first >> p[i].second ; 

    vector<vector<ll>> dp(n,vector<ll> (h+1,INF));
    // dp[i][j]　i番目までの魔法で、jのダメージを与えるときの消費MPの最小値
    //solve
    //dpをINFで埋める
    rep(i,n) dp[i][0] = 0 ; //0のダメージを与えるときのMPは0

    rep(i,n){
        ll atk = p[i].first ;
        ll mp = p[i].second ;
        rep(j,h+1){
            if(j == 0 ) continue; //これがないと死ぬ
            if ( j <= atk ){
                dp[i][j] = mp ;
                if( i != 0 ) chmin(dp[i][j],dp[i-1][j]);
            } else { 
                chmin(dp[i][j],dp[i][j-atk]+mp);
                if( i != 0) chmin(dp[i][j],dp[i-1][j]);
            }
        }
    }
/*イカのコメントアウトを外すと、作られたDPが見れます*/
// rep(i,n){
//     rep(j,h+1){
//         cout << dp[i][j] <<" " ;
//     }
//     cout << endl;
// }
// cout << "above is check" << endl;
    cout << dp[n-1][h] << endl;

}

これは初心者わいの感想というかお気持ちなんですけど、DPをやるときは、 DP[i][j] := i番目までの魔法でjのダメージを与えるときの消費MPの最小値みたいな感じで（手元の考察用紙）に書いておくとだいぶ見通しが良くなると思います。この定義から、出力する答えは ** dp[n-1][h]です(n個の魔法を使ったときに、hダメージを与えるときの最小消費MPはそこにはいってる)

恐らくこのコードはもらうDP??でしたっけ？そんな感じのやつなので、ループ部分がちょっと僕の理解だとごちゃごちゃにしかかけなくて…

例えば、１つめの魔法の攻撃力が１０でDP配列を作っていくとき、本来ならばdp[0][j-10]を見たいんですけど、j == 1のとき（つまり、1つ目の魔法までを使ってダメージ1を与えるときのMPの最小値を求めたい) 配列外参照？？っていうか添字が負 dp[0][-9]になってしまうので、攻撃力がjよりも大きい間は

if ( j  <= atk ){
    dp[i][j] = mp ;
    chmin(dp[i][j],dp[i-1][j]);
}

chminは　最小値を更新するってことです。グローバルに？定義してます。また、j = 0　、つまりダメージ０を与えるときのMPの最小値は0なので、そこを更新させないようにする注意が必要です。作られたDPテーブルは、コードの後ろの方のコメントアウトを外すと見れます。

一次元DPでやってみよう

int main()
{
    //入力
    ll h , n ;
    cin >> h >> n ;//定期の体力はh
    vector<ll> dp(h+1,INF);
    dp[0] = 0 ;

    for(int i = 0 ; i < n ; i ++ ) {
        ll atk , mp;
        cin >> atk >> mp;
        for(int i = 1 ; i <= h ; i ++ ){
            if( i < atk ){
                chmin(dp[i], mp );
            } else {
                chmin(dp[i], dp[i-atk] + mp);
            }
        }
    }
    cout << dp[h] << endl;
}

今度は、一次元DPです。前回は、一度入力を保存してから、atk = p[i].first;みたいな感じで受け取っていたんですけど、今回は入力を受け取りつつ作成していきました。ループの回数はおそらく変わっていないと思います。 DP[i]の定義は、[i]のダメージを与えるときの消費MPの最小値です。よって、出力する答えは　dp[h] です。

結局やってることは、配列をn行h+1列で作っていたものを1行h+1列にしただけです。。先程のときと同じように、添字で死なないように、最小値を更新しながら、攻撃力が添字iより大きい間は、今までのMinと現在使おうとしている魔法でのMinを取るって感じですね。。

それ以降はdp[i-atk] + mp と今までの最小を取っていくってノリ。

えーん　説明難しいよお破滅してしまえ