yukicoder : No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん

iwiを思い出す問題。
https://yukicoder.me/problems/no/1542

問題

p,o,nで構成されるN文字の文字列Sが与えられる。

Sを、"ponpon"から初めて以下の手順を任意回数行って作ることを考える。

• "pon"をどこかに挿入する
• "p","o","n"のどれかをどこかに挿入する

前者の処理を、最大何回行えるか。

解法

f(L,R) := S[L...R)を構成するときに、"pon"の挿入回数の最大値
とする。"ponpon"から始めるので、ponの最小挿入回数は少なくとも2回必要である。
そこで、f(0,x)≧1、f(x,N)≧1となるxを総当たりし、f(0,x)+f(x,N)-2の最大値を求めよう。

f(L,R)は以下の最大値を考える。

• もともと2つの文字列を連結した形になる場合、f(L,M)+f(M,R)
• S[L]="p", S[M]="o"、S[R-1]="n"の場合、"pon"を挿入した後、S[L+1...M)及びS[M+1...R)を構築したと考えられる。
  • そこで、Mを総当たりしつつ1+f(L+1,M)+f(M+1,R-1)を求める。

int N;
string S;

int dp[505][505];

int hoge(int L,int R) {
	if(R-L<3) return 0;
	if(dp[L][R]!=-1) return dp[L][R];
	int ret=0;
	
	for(int M=L+1;M<R;M++) ret=max(ret,hoge(L,M)+hoge(M,R));
	
	if(S[L]=='p'&&S[R-1]=='n') {
		for(int M=L+1;M<R-1;M++) if(S[M]=='o') {
			ret=max(ret,1+hoge(L+1,M)+hoge(M+1,R-1));
		}
	}
	
	return dp[L][R]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	MINUS(dp);
	int ma=-1;
	for(i=0;i<N;i++) {
		x=hoge(0,i+1);
		y=hoge(i+1,N);
		if(x==0||y==0) continue;
		ma=max(ma,x+y-2);
	}
	
	cout<<ma<<endl;
	
}

まとめ

タイトルの「ぽん」の回数に何か意味があるのかな。単にリズムのよさそうな回数？