P1073 -- Password

时间限制：1000MS

内存限制：65536KB

Description

真真要给很多朋友发生日party的邀请函 但是但是 一个邮箱发的速度实在是让人难以忍受 真是难以忍受啊 所以 所以 他要使用一项非常牛叉的计划—— 那就是 使用两个邮箱~~ 两个邮箱的密码是不一样的 为了更加方便的记忆 可爱的真真想到了一个好办法 他要有新的密码。 真真觉得，如果原来的密码是新密码的子序列，那该多好啊 但是真真懒得记那么长的密码 所以他希望 这个新密码 要短一点 短一点 短点 短 ！

Input Format

总共两行 每行一个密码 密码长度小于3000

Output Format

输出就一个数字 那就是新密码的最短长度

Sample Input

abac

Sample Output

3

Hint

【题解】

序列DP，答案为len1+len2-LCS

1 #include 
      
        2 #include 
       
         3 #include 
        
              4 #define MaxLen 3001 5 using namespace std; 6 char st1[MaxLen],st2[MaxLen]; 7 int ans[MaxLen][MaxLen]; 8 void Work(void) { 9     int i,j;10     for(i=1;st1[i-1]!=0;i++)11         for(j=1;st2[j-1]!=0;j++) {12             ans[i][j]=max(ans[i-1][j],ans[i][j-1]);13             if (st1[i-1]==st2[j-1])14                 ans[i][j]=max(ans[i][j],ans[i-1][j-1]+1);15         }16     printf("%d\n",i+j-2-ans[i-1][j-1]);17 }18 int main(){19     scanf("%s %s",st1,st2);20     Work();21     return 0;22 }