本番2時間デバッグしてバグが取れなかった問題。
http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi
問題
iとwで構成される文字列Sが与えられる。
S中に文字列'iwi'があればそれを取り除くことができる。
Sから最大'iwi'を何回取り除けるかを答えよ。
解法
各文字から初めて、最大何文字取り除けるかをDPで求める。
以下の条件の時、最大で3K文字を取り除くことができる。
Kを大きくしながらDPしていけばよい。
- 3K文字分の部分文字列の先頭および末尾はi
- 部分文字列の途中にwがあり、先頭のiとwの間およびwと末尾のiの間はすべて取り除ける
後者の条件は、iiwiiwiwiにおける真ん中のiwiiwiの様に、取り除けるパターンが複数ある場合に注意。
自分はこれを忘れてずっとデバッグしてた。
各文字を先頭に最大で取り除ける文字数がわかったら、あとは先頭からgreedyに取り除いていけばよい。
int L; string S; int reducable[322][322]; int mama[322]; void solve() { int f,r,i,j,k,l, x,y,z; cin>>S; L=S.size(); for(l=2;l<L;l+=3) { FOR(x,L) if(S[x]=='i') { z=x+l; if(z>=L || S[z]!='i') continue; for(y=x+1;y<z;y++) if(S[y]=='w') { if((reducable[x+1][y]||(x+1==y)) && (reducable[y+1][z]||(y+1==z))) reducable[x][z+1] = (l+2)/3; } for(y=x+1;y<z;y++) if(reducable[x][y] && reducable[y][z+1]) reducable[x][z+1] = (l+2)/3; } } for(x=L-1;x>=0;x--) { mama[x]=mama[x+1]; for(y=x;y<=L;y++) mama[x]=max(mama[x], reducable[x][y]+mama[y]); } return _P("%d\n",mama[0]); }