USACO5.4-Character Recognition

题目大意是字符串识别
一道细节很繁琐的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 <stack>
  2 #include <iostream>
  3 #include <stdio.h>
  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/20;i++)
 66     {
 67         for(int j=0;j<20;j++)
 68         {
 69             scanf("%s",ch[i][j]);
 70 
 71         }
 72     }
 73 
 74     freopen("charrec.in","r",stdin);
 75     freopen("charrec.out","w",stdout);
 76 
 77     cin>>n;
 78 
 79     for(int i=0;i<n;i++)
 80         scanf("%s",mat[i]);
 81 
 82     // 初始化dif数组
 83     for(int i=0;i<27;i++)
 84         for(int j=0;j<20;j++)
 85         {
 86             for(int k=0;k<n;k++)
 87             {
 88                 dif[i][j][k]=getDif(i,j,k);
 89             }
 90         }
 91 
 92     // 初始化cost
 93     for(int i=0;i<n;i++) // 从第i行开始匹配
 94     {
 95         cost[i][R19]=cost[i][R20]=cost[i][R21]=INF;
 96         for(int j=0;j<27;j++) // 第j个字符
 97         {
 98             if(i+19<n+1)
 99             {
100                 for(int k=0;k<20;k++) // 删掉行数
101                 {
102                     if(cost[i][R19]>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<n+1)
110             {
111                 if(cost[i][R20]>getCost(j,i,-1))
112                 {
113                     cost[i][R20]=getCost(j,i,-1);
114                     optimalCh[i][R20]=j;
115                 }
116             }
117             if(i+21<n+1)
118             {
119                 for(int k=0;k<21;k++) // 多出的行数
120                 {
121                     if(cost[i][R21]>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     // DP
137     for(int i=21;i<n;i++) // 匹配的最后一行为i
138     {
139         if(d[i-19]+cost[i-18][R19]<d[i])
140         {
141             d[i]=d[i-19]+cost[i-18][R19];
142             step[i]=19;
143         }
144         if(d[i-20]+cost[i-19][R20]<d[i])
145         {
146             d[i]=d[i-20]+cost[i-19][R20];
147             step[i]=20;
148         }
149         if(d[i-21]+cost[i-20][R21]<d[i])
150         {
151             d[i]=d[i-21]+cost[i-20][R21];
152             step[i]=21;
153         }
154     }
155 
156     stack<int> 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<<endl;
170     return 0;
171 }