裏紙

ほぼ競プロ、たまに日記

CF 682 D - Alyona and Strings

問題

Problem - D - Codeforces

問題概要

アルファベットの小文字のみで構成される文字列s,tがあり、長さはそれぞれn,mである。今、sの中から共通部分を持たず、それぞれが空ではない部分文字列をk個選ぶ。そして、その選んだk個の部分文字列が、tの中にも同じ順番で現れるように選びたい。このように部分文字列を選ぶ時、k個の部分文字列の長さの和の最大値を求めよ。

形式的に記述すると、空ではない文字列p_1 , p_2 , ... , p_kがあり、sa_1 p_1 a_2 p_2 a_3 ... p_{k-1} a_k p_k a_{k+1}のような形で表されて、tb_1 p_1 b_2 p_2 b_3 ... p_{k-1} b_k p_k b_{k+1}のような形で表せるように部分文字列をk個を選び、その長さの和を最大化せよということである( a_i , b_iは空であっても良い)。

  •  1 \le n,m \le 1000
  •  1 \le k \le 10
  • k個の部分文字列を適切に選ぶ方法が1通り以上存在する

イデア

DPで解く。dp[i][j][ct][end] = sのi文字目、tのj文字目まででct個の部分文字列を選ぶ時の部分文字列の長さの和の最大値とする。endに関しては、sのi文字目とtのj文字目が最大値を取るときに部分文字列として含まれていれば1、そうでないときは0を取ることにする。

さて、いま dp[i ][j ][ct ][end ] の状態にいる時、次の遷移として考えられるのはsを1文字すすめる、またはtを1文字すすめるというのがまず考えられる。このときはどちらも次の状態はend=0となるので遷移の形としては、それぞれ、sを1文字すすめるときは dp[i+1 ][j ][ct ][0 ] = max(dp[i+1 ][j ][ct ][0 ] , dp[i ][j ][ct ][end ])、tを1文字すすめるときは dp[i ][j+1 ][ct ][0 ] = max(dp[i ][j+1 ][ct ][0 ] , dp[i ][j ][ct ][end ])ということになる。

また、 s_i = t_jであるときには、部分文字列として選択するという遷移も考えられる。ここで、endが効いてくる。end = 1の時は、ct番目の部分文字列を継続させる選択肢と新たにct+1番目の部分文字列の先頭とする選択肢がありえて、end=0の時は後者のみを選択可能なので、継続させるときの遷移は dp[i+1 ][j+1 ][ct ][1 ] = max(dp[i+1 ][j+1 ][ct ][1 ] , dp[i ][j ][ct ][1 ] +1) 、新たに作るときの遷移は dp[i+1 ][j+1 ][ct+1 ][1 ] = max(dp[i+1 ][j+1 ][ct+1 ][1 ] , dp[i ][j ][ct ][end ] +1)となる。

この遷移を実装していけばよい。本番も明らかに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;
}