一番長い共通サブシーケンスの変形が良いです.

問題の由来:
http://hihocoder.com/discuss/question/2111
題意分析
アルファベットのみを含む2つの文字列A,B,A,Bの2つの文字列の最長共通サブシーケンスを指定します.サブシーケンスを構成するサブストリングの長さはすべて3以上でなければなりません.
例えば、"abcdefghijklmn"および"ababceghjklmn"のように、最も長い題意要求を満たすサブシーケンスは"abcjklmn"であり、これは、共通のサブストリング"abc"および"jklmn"によって構成される.
ここでは と の違いに注意します.
サブストリング:連続的な要素サブシーケンス:不連続要素例えば、"abcdefghijklmn"と"ababceghjklmn"という最長の共通部分列は、"jklmn"だけです.
アルゴリズム解析
まず古典的なテーマを復習します.
アルファベットだけを含む2つの文字列A,Bを指定して、A,Bの2つの文字列の最も長い共通のサブシーケンスを求めます.
例えば、"abcde"および"abdfg"の最長の共通サブシーケンスは"abd"である.
一番長い公共サブシーケンスに対して、解法は

dp[0][0..j] = 0    //   
dp[0..i][0] = 0    //   
For i = 1 .. n
    For j = 1 .. m
        If a[i] == b[j] Then
            dp[i][j] = dp[i - 1][j - 1] + 1
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

このテーマは、最長の公共サブシーケンスに条件を加えたものである.最長の共通サブシーケンスを構成する各サブストリングの長さは、3以上でなければならない.
簡単な考え:一番長い公共サブシーケンスを求めて、その中の長さが3より小さい部分を削除します.
明らかに、これは間違っています.
一例としては、"aaabaa"および"acaaaca"の最長男シーケンスが"aaaaa"である.その対応関係は:

a aaba a
acaa aca

"acaaaca"の中で最初のアルファベットaの長さは1ですので、それを削除したいです.対応する私達も"aaabaa"の中で最初のアルファベットaを外しました.

.  aaba a
. caa aca

このとき、"aaabaa"および"acaaaca"の共通サブシーケンスを構成する3つのサブストリングは"aa"、"a"、"a"であり、長さは3よりも小さいので、全部削除すれば、新しい共通サブシーケンス長は0になる.
これは明らかに正しくないです.実際には題意の要求に合致する公共サブシーケンスがあります.

   aaa baa
ac aaa ca

長さ3の共通サブシーケンスが含まれている.
最大共通サブシーケンスの結果を再度処理することは不可能であり、共通サブシーケンスを計算するアルゴリズムから着手するしかない.
まず、aのi番目の文字を最後とするプレフィックスと、bのj番目の文字を最後とするプレフィックス*の共通のサフィックスの長さをf[i][j]で表す前処理をしても良いと思います.このように見えますが、回りくどいです.例を挙げてください.
a="abcd"およびb="acbc".f[3][4]は、a[1.3]とb[1.4]の共通の接尾辞の長さを表しており、a[1.3]="abc"、b[1.4]="acbc"であり、共通の接尾辞は"bc"であるので、f[3][4]=2.
前処理の疑似コードは次の通りです.

For i = 1 .. n
    For j = 1 .. m
        If a[i] == b[j] Then
            f[i][j] = f[i - 1][j - 1] + 1
        Else
            f[i][j] = 0
        End If
    End For
End For

この前処理の配列があり、元の最大共通サブシーケンスでこのような改良を行うことができます.

dp[0][0..j] = 0    //   
dp[0..i][0] = 0    //   
For i = 1 .. n
    For j = 1 .. m
        If f[i][j] >= 3 Then    //   
            dp[i][j] = dp[i - f[i][j]][j - f[i][j]] + f[i][j]
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

この改良の意味は,長さが3より大きいサブストリングが出現すると,このサブストリングを直接に我々のサブシーケンスに組み込むことである.
この改善を加えると、サンプルのデータが通りますので、問題ないように見えます.
しかし事実はそうではなく、このテーマには落とし穴が隠されています.
例えば、"abcdef"と"abcxcdef".
私たちのアルゴリズムによれば、上記の例で算出された結果は4であるが、その実際の結果は6であるべきであり、すなわち"abc"と"def"の2つの共通のサブストリングからなるサブシーケンスである.
エラーの原因はどこですか?文字列"cdef"にあります.
私たちが計算した4は、"cdef"を一つの全体と見なし、"abcdef"を"ab"と"cdef"に分割したからです.
DPの過程でf[6][7]=4はdp[6]=dp[2][3]+4を使っていますが、dp[2][3]=0はdp[6][7]=4です.

ab  cdef
abcxcdef

f[6][7]を3とし、dp[6]=dp[3]、[4]+3とし、dp[3]、[4]=3とし、dp[6][7]=6を得た.

abc  def
abcxcdef

つまり、f[i][j]>3のサブストリングを分割すれば、より優れた場合があります.したがって、さらなる改善が必要です.

dp[0][0..j] = 0    //   
dp[0..i][0] = 0    //   
For i = 1 .. n
    For j = 1 .. m
        dp[i][j] = 0
        If f[i][j] >= 3 Then    //   
            For k = 3 .. f[i][j]    //       
                dp[i][j] = Max(dp[i][j], dp[i - k][j - k] + k)
            End For
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

しかし、このような改良により、アルゴリズム全体の時間複雑度がO(n^3)に変化し、n=2100でタイムアウトする場合があります.
このアルゴリズムをさらに改善する方法を考えてみましょう.以上のアルゴリズムの複雑度が高いところは、各(i,j)に対して、dp［i］［j］を計算するために、エニュメレーション分割長さkを必要とすることである.

For k = 3 .. f[i][j]    //       
    dp[i][j] = Max(dp[i][j], dp[i - k][j - k] + k)
End For

このステップは実際に計算されたmax{dp[i-k][j-k]+k}, k=3..f[i][j]です.それをdp 1[i][j]と覚えてもいいです.

dp1[i][j] = max{dp[i-k][j-k]+k} = max{dp[i-3][j-3]+3, dp[i-4][j-4]+4, dp[i-5][j-5]+5, ... }

同時に

dp1[i-1][j-1] = max{dp[i-1-3][j-1-3]+3, dp[i-1-4][j-1-4] + 4, dp[i-1-5][j-1-5]+5 ... }
    = max{dp[i-4][j-4]+3, dp[i-5][j-5]+4, dp[i-6][j-6]+5, ... }

dp 1[i][j]の展開式ではdp[i-3][j-3]+3を除いて、dp 1[i-1][j-1]の各項目に対応しており、ちょうど1つ大きいことが分かります.したがって、実際にdp[i-1][j-1]計算時に列挙した分割長さは、再度計算する必要はありません.

dp1[i][j] = max{dp1[i-1][j-1] + 1, dp[i-3][j-3]+3}

最後に、私たちの新しい疑似コードは、dp[i][j][0]が、上記の分析におけるdp[i]、[j]に対応し、dp[i]、[j]、[1]がdp 1[i][j]:

dp[0][0..j][0..1] = 0    //   
dp[0..i][0][0..1] = 0    //   
For i = 1 .. n
    For j = 1 .. m
        dp[i][j][1] = 0
        If f[i][j] >= 3 Then    //   
            dp[i][j][1] = Max(dp[i][j][1], dp[i - 3][j - 3][0] + 3)     //    3   
            If (f[i][j] > 3) Then
                //  dp[i-1][j-1][1]       ，    (i,j)  (i-1,j-1)  
                dp[i][j][1] = Max(dp[i][j][1], dp[i - 1][j - 1][1] + 1)
            End If
        End If
        dp[i][j][0] = Max(dp[i-1][j][0], dp[i][j-1][0], dp[i][j][1])
    End For
End For

これで私のこの問題も完璧に解けました.
結果分析
このテーマは経典の動的計画テーマ「最長公共サブシーケンス」の上で少し修正しました.条件を一つだけ追加しましたが、難易度が多くなりました.複雑さはO(n^2)の正しいアルゴリズムを考えるのは簡単ではないので、詳細な分析が必要です.油断するといろいろな落とし穴にはまります.
多くの選手がクラシックの長男シーケンスの改良アルゴリズムを考えて80点を獲得しました.
残りのテストポイントはアルゴリズム分析で言及された落とし穴に対応していますので、このような特殊な例を見つけることができるかどうかがこの問題を解決する鍵になります.
しかし、マイクロソフトの出題者はあまり困らないと思っているようです.データはあまり強くないです.実際の試合では、O(n^3)のアルゴリズムも満点を取り、最終的にはこのテーマの通過率は9%となります.
多くのO(N^2)のプログラムは"babad"と"babacabad"のデータのセットを通してはいけません.

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2200;
int d[N][N][2];
int f[N][N],n,m;
char str[N],src[N];
int dp(){
  memset(d,0,sizeof(d));
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        d[i][j][1]=0;
        if(f[i][j]>=3) d[i][j][1]=d[i-3][j-3][0]+3;
        if(f[i][j]> 3) d[i][j][1]=max(d[i][j][1],d[i-1][j-1][1]+1);
        d[i][j][0]=max(max(d[i-1][j][0],d[i][j-1][0]),d[i][j][1]);
  }
  return d[n][m][0];
}
int main()
{
   while(scanf("%s %s",str+1,src+1)!=EOF){
       n = strlen(str+1),m=strlen(src+1);
       for(int i=1;i<=n;i++) f[i][0]=0;
       for(int i=1;i<=m;i++) f[0][i]=0;
       f[0][0]=0;
       for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++){
            if(str[i]==src[j]) f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=0;
       }
       printf("%d
",dp());
   }
   return 0;
}