CF 682 D - Alyona and Strings
問題
問題概要
アルファベットの小文字のみで構成される文字列があり、長さはそれぞれである。今、の中から共通部分を持たず、それぞれが空ではない部分文字列を個選ぶ。そして、その選んだ個の部分文字列が、の中にも同じ順番で現れるように選びたい。このように部分文字列を選ぶ時、個の部分文字列の長さの和の最大値を求めよ。
形式的に記述すると、空ではない文字列があり、がのような形で表されて、がのような形で表せるように部分文字列を個を選び、その長さの和を最大化せよということである(は空であっても良い)。
- 個の部分文字列を適切に選ぶ方法が1通り以上存在する
アイデア
DPで解く。dp[i][j][ct][end] = sのi文字目、tのj文字目まででct個の部分文字列を選ぶ時の部分文字列の長さの和の最大値
とする。end
に関しては、sのi文字目とtのj文字目が最大値を取るときに部分文字列として含まれていれば1、そうでないときは0を取ることにする。
さて、いまの状態にいる時、次の遷移として考えられるのはsを1文字すすめる、またはtを1文字すすめるというのがまず考えられる。このときはどちらも次の状態はとなるので遷移の形としては、それぞれ、sを1文字すすめるときは、tを1文字すすめるときはということになる。
また、であるときには、部分文字列として選択するという遷移も考えられる。ここで、end
が効いてくる。の時は、番目の部分文字列を継続させる選択肢と新たに番目の部分文字列の先頭とする選択肢がありえて、の時は後者のみを選択可能なので、継続させるときの遷移は、新たに作るときの遷移はとなる。
この遷移を実装していけばよい。本番も明らかにDPだろうなあとは思っていたが、最後のend
を変数として用意するアイデアが無かった...
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second int dp[1002][1002][12][2]={0}; int main() { int n,m,k; string s,t; cin >>n >>m >>k >>s >>t; rep(i,n+1)rep(j,m+1)rep(ct,k+1) { if(i<n && j<m && s[i]==t[j]) { // 前の部分文字列の継続 if(ct>0) dp[i+1][j+1][ct][1] = max(dp[i+1][j+1][ct][1], dp[i][j][ct][1]+1); // 新たな部分文字列 rep(end,2) dp[i+1][j+1][ct+1][1] = max(dp[i+1][j+1][ct+1][1], dp[i][j][ct][end]+1); } rep(end,2) { // sを1文字すすめる if(i<n) dp[i+1][j][ct][0] = max(dp[i+1][j][ct][0], dp[i][j][ct][end]); // tを1文字すすめる if(j<m) dp[i][j+1][ct][0] = max(dp[i][j+1][ct][0], dp[i][j][ct][end]); } } cout << max(dp[n][m][k][0], dp[n][m][k][1]) << endl; return 0; }