题目大意是字符串识别

一道细节很繁琐的DP,要用到很多数组

一开始还真看不出是DP,后来参考了别人的代码,然后又按自己的思路重头到尾写了,虽然速度不咋的

Executing...

Test 1: TEST OK [0.008 secs, 6504 KB]

Test 2: TEST OK [0.008 secs, 6504 KB]

Test 3: TEST OK [0.019 secs, 6504 KB]

Test 4: TEST OK [0.035 secs, 6504 KB]

Test 5: TEST OK [0.084 secs, 6504 KB]

Test 6: TEST OK [0.116 secs, 6504 KB]

Test 7: TEST OK [0.167 secs, 6504 KB]

Test 8: TEST OK [0.192 secs, 6504 KB]

Test 9: TEST OK [0.178 secs, 6504 KB]

All tests OK.

YOUR PROGRAM ('charrec') WORKED FIRST TIME! That's fantastic

-- and a rare thing. Please accept these special automated

congratulations.

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #define R19 0  5 #define R20 1  6 #define R21 2  7 #define INF 1000000000  8 using namespace std;  9  10 char ch[28][22][22]; 11 char mat[1210][22]; 12 int dif[28][22][1210]; 13 int cost[1210][4]; // cost[i][j]表示从mat的第i行开始匹配j行得到的最小差距 14 int optimalCh[1210][4]; // optimalCh[i][j]表示从mat的第i行开始匹配j行最优的匹配字符 15 int d[1210]={
   0}; // d[i]表示匹配到第i行所得到的最小差距 16 int step[1210]; // step[i]表示第i行开始的最优匹配的字符行数 17 // 得到行数中不同的个数 18 /* 19 num为第几个字符 20 l1为num字符的行数 21 l2为mat的行数 22 */ 23 int getDif(int num,int l1,int l2) 24 { 25     int sum=0; 26     for(int i=0;i<20;i++) 27     { 28         if(ch[num][l1][i]!=mat[l2][i]) 29             sum++; 30     } 31     return sum; 32 } 33  34 // num为字符，l1为mat开始匹配的行数，del为删除了哪一行 35 int getCost(int num,int l1,int del) 36 { 37     int sum=0; 38     for(int i=0,p=0;p<19;i++,p++) 39     { 40         if(i==del) 41             i++; 42         sum+=dif[num][i][l1+p]; 43     } 44     return sum; 45 } 46  47 int getCost2(int num,int l1,int del) 48 { 49     int sum=0; 50     for(int i=0,p=0;i<20;i++,p++) 51     { 52         if(p==del) 53             p++; 54         sum+=dif[num][i][p+l1]; 55     } 56     return sum; 57 } 58  59  60 int main() 61 { 62     freopen("font.in","r",stdin); 63     int n; // 行数 64     cin>>n; 65     for(int i=0;i
        
         >n; 78  79     for(int i=0;i
         
          getCost(j,i,k))103                     {104                         cost[i][R19]=getCost(j,i,k);105                         optimalCh[i][R19]=j;106                     }107                 }108             }109             if(i+20
          
           getCost(j,i,-1))112 {113 cost[i][R20]=getCost(j,i,-1);114 optimalCh[i][R20]=j;115 }116 }117 if(i+21
           
            getCost2(j,i,k))122 {123 cost[i][R21]=getCost2(j,i,k);124 optimalCh[i][R21]=j;125 }126 }127 }128 }129 }130 131 fill_n(d,n+5,INF);132 // 初始值133 d[18]=cost[0][R19];step[18]=19;134 d[19]=cost[0][R20];step[19]=20;135 d[20]=cost[0][R21];step[20]=21;136 // DP137 for(int i=21;i
            

S;157 158 for(int p=n-1;p!=-1;p=p-step[p])159 {160 S.push(optimalCh[p-step[p]+1][step[p]-19]);161 }162 163 while(!S.empty())164 {165 int tmp=S.top();166 S.pop();167 printf("%c",tmp==0?' ':tmp-1+'a');168 }169 cout<