TIOJ 1118 非常速配 ( 92北市賽prob 4 )

poao899    0K    31MS    G++     0.62K     2009-11-10 13:33:55                                                 .


唔LCS

不過每次都被LCS初始化表|||   像是TIOJ 1385 芳佳的打工(汗


//**************************************

//92 prob4

#include<stdio.h>
#include<string.h>
int dp[20][20];
char n1[20],n2[20];
main(){
 n1[0]=n2[0]=1;
 while(gets(n1+1)){
  gets(n2+1);
  int i,j;
  for(int i=0;i<=strlen(n1+1);i++)
   dp[i][0]=-3*i;
  for(int j=0;j<=strlen(n2+1);j++)
   dp[0][j]=-3*j;
  for(i=1;n1[i];i++)
   for(j=1;n2[j];j++){
    if(n1[i]==n2[j]){
     dp[i][j]=(dp[i-1][j-1]+10)>?(dp[i-1][j]-3)>?(dp[i][j-1]-3);
    }
    else{
     dp[i][j]=(dp[i-1][j-1]-5)>?(dp[i-1][j]-3)>?(dp[i][j-1]-3);
    }
   }
  printf("%.2lf%%\n",(double)dp[strlen(n1+1)][strlen(n2+1)]*10/strlen(n1+1));
 }
}