bzoj 1789:[Ahoi 2008]Necklace Y型ネックレス欲張り

1789:[Ahoi 2008]Necklace Y型ネックレス
Time Limit:20 Sec  メモリLimit:256 MB
タイトル接続
http://www.lydsy.com/JudgeOnline/problem.php?id=1789
Description
歓楽島には珍しいアトラクションがたくさんあります.しかし、彼らはとても楽しかったです.今彼らはレースネックレスのゲームをしています.誰が一番早くできますか?これは普通のネックレスではなく、Y型のネックレスです.ネックレスの真ん中に大きな真珠が結合点としてあります.大きな真珠から3つのチェーンがつながっています.試合のルールはこうです.毎回三つのチェーンの中の一つの端から宝石を一つ取ったり、宝石を一つ取り付けたりすることができます.一回の操作といいます.何回も操作して、最後に三つのチェーンはまったく同じです.試合に勝ちたいなら、できるだけ少ない操作回数を使うしかないです.すべての宝石が無数にあると仮定して、しかもチェーンは十分に長いです.試合に勝つためにちょっと手伝ってもらえますか?注:Y型ネックレスの宝石数には特に要求がないので、すべての宝石を取り外しても納得できるプランです.
Input
全部で3行あります.Y型のネックレスを表している3つのチェーンは、1ラインごとに数字Nがあります.最初の時にこのチェーンにはN個の宝石(N<=50)が連結されています.その後はスペースで、N個の'A'と'Z'の間の文字があります.このチェーンの上の宝石を表しています.それぞれのアルファベットには異なる宝石が示されています.この文字列の一番左の文字は大真珠に一番近い宝石を表しています.一番右の文字はチェーンの端にある宝石です.
 
Output
一つの整数だけが必要な最低操作回数を表します.
 
Sample Input

3 CAT
 3 TAC
 5 CATCH

Sample Output

8

HINT
 ヒント:100%のデータのうち、N<=50.50%のデータのうち、N<=20.
題意
 
クイズ:
任意の二つの列に対して、最初から一番長い公共の文字列を求めて、貪欲に削除したらいいです.
コード:
 

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)  
#define maxn 2000001
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************
int len[10];  
char str[10][100];  
int main()  
{  
    for(int i=1;i<=3;i++)  
    {  
        scanf("%d%s",&len[i],str[i]+1);  
    }  
    int ans=len[1]+len[2]+len[3];  
    int co,res,tmp;  
    for(int i=1;i<=3;i++)  
    {  
        for(int j=i+1;j<=3;j++)  
        {  
            tmp=co=0;  
            for(;co<min(len[i],len[j])&&str[i][co+1]==str[j][co+1];co++);  
            int k=6-i-j;  
            res=len[i]-co+len[j]-co;  
   
            for(;tmp<min(len[k],co)&&str[i][tmp+1]==str[k][tmp+1];tmp++);  
   
            if(co>=tmp) res+=(co-tmp)+len[k]-tmp;  
               
            ans=min(ans,res);  
   
        }  
    }  
    printf("%d
",ans);  
    return 0;  
}