また精進スピード低下。。。
さっき書いた記事の流れで通したやつと、蟻本セット「基本的な動的計画法」から一問です。
あしたTopCoderというのに精進スピード低下してます。
あとDP解けた時の達成感が尋常じゃない。
AOJ 0528
あのあと有為さんがローリングハッシュをつかった解法が提示してくださったりしました。
基本どうやら接頭辞木を使うほうが稀なようで、たしかに接頭辞木は線形時間で終わる利点がありますが使うのは実際の開発現場だけ・・・といった感じになるようです(アルゴリズムクイックリファレンスには載ってませんでした・・・)
今回はせっかくなのでqnighyさん解でやりました。これが一般的なようで、一応スライドでも通るらしいですが、とにかく通しました。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char str1[4001], str2[4001]; int main() { while (scanf("%s%s",&str1,&str2)!=EOF) { int res=0; for (int off=-1*(int)strlen(str1); off<=(int)strlen(str2); off++) { int len=0; for (int i=max(off,0); i<min(strlen(str1)+off,strlen(str2)); i++) { if (str1[i-off]==str2[i]) { len++; res=max(res,len); } else { len=0; } } } printf("%d\n",res); } }
PKU 2385
最初の位置が決まっているので移動回数の遇奇で今いる場所が判定できることに注目します。
すると場合分けで比較的簡単なDPを書くことができます。あとはコード参照。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t, w; int fall[1000]; int dp[1000][31]; /* dp[i][j]=i番目までにj回移動した時の最大値(?) dp[0][even]=1(fall[0]=0) 0(fall[0]=1) dp[0][odd]=0(fall[0]=0) 1(fall[0]=1) dp[i][j]=max(dp[i-1][k]+a) */ int main() { memset(dp,0,sizeof(dp)); scanf("%d%d",&t,&w); for (int i=0; i<t; i++) scanf("%d",&fall[i]); for (int i=0; i<t; i++) fall[i]--; for (int i=0; i<w; i++) { if (i%2==fall[0]) dp[0][i]=1; else dp[0][i]=0; } for (int i=1; i<t; i++) for (int j=0; j<=w; j++) { int pos=j%2; int a; if (pos==fall[i]) a=1; else a=0; for (int k=0; k<=j; k++) { dp[i][j]=max(dp[i][j],dp[i-1][k]+a); } // printf("%d%c",dp[i][j],j==w-1?'\n':' '); } int res=0; for (int i=0; i<=w; i++) { res=max(res,dp[t-1][i]); } printf("%d\n",res); }