おはようございます。
なんか書きたくなったので。
こんなまとめとか作っている僕ですが、正直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の真の難しさだと感じました。
はい、まとめちゃいました。続けるのが怖くなりました。
とりあえずなれるぐらい頑張っていこうと思います。
