foj2024

电玩女神 2021-12-22 10:01 99阅读 0赞

[http://acm.fzu.edu.cn/problem.php?pid=2024][http_acm.fzu.edu.cn_problem.php_pid_2024]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

\#include < stdio.h >   
\#include < string .h >   
 \#define  M 1010   
 int  c\[M\]\[M\];  
 int  f\[M\]\[M\];  
  
 int  min( int  a, int  b, int  c)  
\{  
 int  z = (a < b) ? a:b;  
 if (z < c) return  z;  
 else  return  c;  
\}  
  
 int  Max( int  a , int  b)  
\{  
 return  a > b ? a:b;  
\}  
 void  LCS( char  aa\[\],  char  bb\[\],  int  x,  int  y)  
\{  
 int  i,j;  
 for (i = 0 ;i <= x;i \++ )  
c\[i\]\[ 0 \] = 0 ;  
 for (j = 0 ;j <= y;j \++ )  
c\[ 0 \]\[j\] = 0 ;  
  
 for (i = 1 ;i <= x;i \++ )  
 for (j = 1 ;j <= y;j \++ )  
\{  
 if (aa\[i \- 1 \]  ==  bb\[j \- 1 \]) c\[i\]\[j\]  = c\[i \- 1 \]\[j \- 1 \] \+ 1 ;  
 else  c\[i\]\[j\] = Max(c\[i\]\[j \- 1 \],c\[i \- 1 \]\[j\]);  
\}  
\}  
 int  main()  
\{  
 char  a\[M\],b\[M\];  
 int  L1,L2;  
 int  t;  
 int  k = 0 ;  
scanf( " %d " , & t);  
 while (t \-- )  
\{  
scanf( " %s %s " ,a,b);  
L1 = strlen(a);  
L2 = strlen(b);  
LCS(a,b,L1,L2);  
 int  xx = c\[L1\]\[L2\];  
 int  ans = 0 ;  
 int  i,j;  
  
f\[ 0 \]\[ 0 \] = 0 ;  
 for (i = 0 ;i <= L1;i \++ )  
f\[i\]\[ 0 \] = i;  
 for (j = 0 ;j <= L2;j \++ )  
f\[ 0 \]\[j\] = j;  
  
 for (i = 1 ;i <= L1;i \++ )  
 for (j = 1 ;j <= L2;j \++ )  
\{  
 if (a\[i \- 1 \] == b\[j \- 1 \])  // 转移方程    
  f\[i\]\[j\] = f\[i \- 1 \]\[j \- 1 \];  
 else  f\[i\]\[j\] = min(f\[i \- 1 \]\[j \- 1 \] \+ 1 ,f\[i \- 1 \]\[j\] \+ 1 ,f\[i\]\[j \- 1 \] \+ 1 );  
\}  
  
printf( " Case %d: LCS=%d EditStep=%d\\n " , \++ k,xx,f\[L1\]\[L2\]);  
  
\}  
 return  0 ;  
\}

转载于:https://www.cnblogs.com/FCWORLD/archive/2011/05/02/2034242.html

[http_acm.fzu.edu.cn_problem.php_pid_2024]: http://acm.fzu.edu.cn/problem.php?pid=2024
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/aed31328ecdf45d2bb11252a7d916faf.png