[ブルーブリッジ杯2016初戦]パスワードが外れた

テーマはX星の考古学者が古代に残された暗号を発見した.これらの暗号はA,B,C,Dの4種類の植物の種子からなる配列である.よく分析すると、これらの暗号列は当初は前後対称だったはずだ.(ミラー列ということです).長い間、多くの種が脱落していたため、ミラーの特徴を失う可能性があります.現在見ている暗号列を指定し、当初の状態から少なくともどれだけの種が脱落しなければならないかを計算して、現在の姿になる可能性があります.複数のテストデータが入力され、各グループについて測定されます.試験データは1行入力し、現在見ている暗号列(長さが1000以下)の出力が各試験データに対して1つの正の整数を出力することを要求し、少なくともどれだけのシードが脱落したかを示す.サンプル入力ABCBA ABDCBABCサンプル出力0 3
正解は、文字列長からその文字列とその文字列の逆順を引いた最長共通サブシーケンスの長さ、例えばABCBA長が5逆順ABCBA(それ自体)LCSがABCBA長が5であるので結果は5-5=0 ABDCBABC長が10逆順CBABCDCDBA LCSがABCDCBA長が7であるので結果は10-7=3となる
**
アルゴリズムの正しさは,元の列と逆の列のLCSが最も長い回文サブ列であることである.
**

#include
using namespace std;
typedef long long ll;

int dp[1005][1005];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

    string s;
    while(cin >> s)
    {
        string s2 = "";
        for(int i = 0; i < s.length(); ++i)
        {
            s2 = s[i] + s2;
        }
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= s.length(); ++i)
        {
            for(int j = 1; j <= s2.length(); ++j)
            {
                if(s[i-1] == s2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        cout << s.length() - dp[s.length()][s.length()] << endl;
    }
	return 0;
}