Codeforces 132 C. Logo Turtle

Codeforces 動的計画法

問題

Logo Turtleを1次元で単純化したものを考える。
命令列はF（直進）およびT（反転）からなる。


与えられた命令列をちょうどn文字（同じ文字を2度以上変更してもよい）を変更して、
命令列を全て実行した後、亀が原点から最大でどれだけ遠くまで離れられるか求めよ。

制約条件

命令列の長さ≦100
n≦50

方針

M[i][j][k]を、命令をi文字実行し、j回命令書き換えを使い、向きk（0なら前）の状態での座標の最大値とする。
同様にm[i][j][k]をその状態での座標の最小値とする。


このテーブルを愚直に更新するようなDPで間に合う。

ソースコード

int n,len;
string in;
int M[101][51][2],m[101][51][2];

void run()
{
	cin>>in>>n;
	len=in.size();
	rep(i,101)rep(j,51)rep(k,2)M[i][j][k]=-inf, m[i][j][k]=inf;
	M[0][0][0]=m[0][0][0]=0;
	rep(i,len)rep(j,n+1)rep(k,2){
		for(int l=j;l<=n;l++){
			if((l-j)%2^(in[i]=='F')){
				M[i+1][l][k]=max(M[i+1][l][k],M[i][j][k]+(k?-1:1));
				m[i+1][l][k]=min(m[i+1][l][k],m[i][j][k]+(k?-1:1));
			}
			else{
				M[i+1][l][1-k]=max(M[i+1][l][1-k],M[i][j][k]);
				m[i+1][l][1-k]=min(m[i+1][l][1-k],m[i][j][k]);
			}
		}
	}
	int ans=max(M[len][n][0],M[len][n][1]);
	ans=max(ans,max(-m[len][n][0],-m[len][n][1]));
	cout<<ans<<endl;
}