DPについて色々と思うところを書き綴ってみる

おはようございます。

なんか書きたくなったので。

こんなまとめとか作っている僕ですが、正直DPは苦手です。

今日も今年のJOI予選の4番を今さっき解いて来ましたが、まぁこの程度でも苦しめられますし、なによりDPできないせいで本選は落ちましたし・・・

そこでこうやってDPというものを遠目に見てみようというわけです。

そうですね、話題に出したのでせっかくだからJOIでの今年のDP二問を見比べてなんか色々書いていきましょう。

まず予選のPasta

#include <cstdio>
#include <algorithm>
using namespace std;
#define mod 10000
int day[100];
long long dp[100][3][3];
int main() {
    int n, k; scanf("%d%d",&n,&k);
    for (int i=0; i<k; i++) {
        int a,b; scanf("%d%d",&a,&b);
        day[a-1]=b;
    }
    if (day[0]) {
        dp[0][day[0]-1][0]=dp[0][day[0]-1][2]=1;
    } else {
        dp[0][0][0]=dp[0][1][0]=dp[0][2][0]=1;
        dp[0][0][2]=dp[0][1][2]=dp[0][2][2]=1;
    }
    for (int i=1; i<n; i++) {
        if (day[i]==1) {
            dp[i][0][0]=(dp[i-1][1][2]+dp[i-1][2][2])%mod;
            dp[i][0][1]=dp[i-1][0][0];
            dp[i][0][2]=(dp[i][0][1]+dp[i][0][0])%mod;
        } else if (day[i]==2) {
            dp[i][1][0]=(dp[i-1][0][2]+dp[i-1][2][2])%mod;
            dp[i][1][1]=dp[i-1][1][0];
            dp[i][1][2]=(dp[i][1][1]+dp[i][1][0])%mod;
        } else if (day[i]==3) {
            dp[i][2][0]=(dp[i-1][0][2]+dp[i-1][1][2])%mod;
            dp[i][2][1]=dp[i-1][2][0];
            dp[i][2][2]=(dp[i][2][1]+dp[i][2][0])%mod;
        } else {
            dp[i][0][0]=(dp[i-1][1][2]+dp[i-1][2][2])%mod;
            dp[i][0][1]=dp[i-1][0][0];
            dp[i][0][2]=(dp[i][0][1]+dp[i][0][0])%mod;
            dp[i][1][0]=(dp[i-1][0][2]+dp[i-1][2][2])%mod;
            dp[i][1][1]=dp[i-1][1][0];
            dp[i][1][2]=(dp[i][1][1]+dp[i][1][0])%mod;
            dp[i][2][0]=(dp[i-1][0][2]+dp[i-1][1][2])%mod;
            dp[i][2][1]=dp[i-1][2][0];
            dp[i][2][2]=(dp[i][2][1]+dp[i][2][0])%mod;
        }
    }
    printf("%lld\n",(dp[n-1][0][2]+dp[n-1][1][2]+dp[n-1][2][2])%mod);
}

これは三次元配列を使いますが、再帰での操作をそのままループに落とし込んだだけなので、漸化式はイメージ通りっていう感じの問題ですね。

そして本選の夜店

#include <cstdio>
#include <algorithm>
using namespace std;
int a[3000], b[3000];
int dp[5000];
int main() {
    int n, t, s; scanf("%d%d%d",&n,&t,&s);
    for (int i=0; i<n; i++) scanf("%d%d",&a[i],&b[i]);
    int res=0;
    for (int i=0; i<n; i++) {
        for (int j=t-b[i]; j>=0; j--) {
            if (j<s&&s<j+b[i]) continue;
            dp[j+b[i]]=max(dp[j+b[i]], dp[j]+a[i]);
            res=max(res,dp[j+b[i]]);
        }
    }
    printf("%d\n",res);
}

今度は少し様子が違います。
典型問題に草が生えた程度なのですが、慣れていないと思わぬバグを埋め込んでしまう問題です。
結局二次元配列でやったら（※僕のコードでは）WA出されましたし、よくわかりません（単純に逆ループしてなかっただけかもしれませんがｗ）

さて、このような違いにはなにがあるのか？

はたまたなぜ違いが生まれているのか？

慣れてる人にはこんな疑問など出てこないのでしょうが、それこそがDPの真の難しさだと感じました。

はい、まとめちゃいました。続けるのが怖くなりました。

とりあえずなれるぐらい頑張っていこうと思います。