USACO 5.4 Character Recognition

#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

const char ch[] = "* abcdefghijklmnopqrstuvwxyz";
const int MAX_NUM_FONTS = 28, N = 20, MAX_LINES = 1201, INF = 99999999;
char font[MAX_NUM_FONTS][N + 1][N + 1], line[MAX_LINES][N + 1];
// diff[i][j][k]: difference between the i-th line of the input image and
// the k-th line of the j-th font soure image.
int diff[MAX_LINES][MAX_NUM_FONTS][N + 1];
// cost[i][j]: minimum cost of match between the i-th line and the (j + 19)-th
// line of the input image.
int cost[MAX_LINES][3];
// index of the matching char.
int from[MAX_LINES][3];
int dp[MAX_LINES], opt[MAX_LINES], ans[100];

ifstream fontin("font.in");
ifstream fin("charrec.in");
ofstream fout("charrec.out");

void readFont() {
    int tmp;
    fontin >> tmp;
    string str;
    for (int i = 1; i <= 27;  ++i) {
        for (int j = 1; j <= N; ++j) {
            fontin >> str;
            for (int k = 1; k <= N; ++k) {
                font[i][j][k] = str[k];
            }
        }
    }
}

void readImages(int n) {
    string str;
    for (int i = 1; i <= n; ++i) {
        fin >> str;
        for (int j = 1; j <= N; ++j) {
            line[i][j] = str[j];
        }

        for (int j = 1; j <= 27; ++j) {
            for (int k = 1; k <= N; ++k) {
                for (int t = 1; t <= N; ++t) {
                    if(line[i][t] == font[j][k][t]) continue;
                    ++diff[i][j][k];
                }
            }
        }
    }
}

void preprocess(int n) {
    for (int i = 1; i + 18 <= n; ++i) {
        cost[i][0] = cost[i][1] = cost[i][2] = INF;
        for (int j = 1; j <= 27; ++j) {
            int t = 0;

            for (int k = 1; k < N; ++k) {
                t += diff[i + k - 1][j][k];
            }

            if (t < cost[i][0]) {
                cost[i][0] = t;
                from[i][0] = j;
            }

            for (int k = 19; k; --k) {
                t -= diff[i + k - 1][j][k], t += diff[i + k - 1][j][k + 1];
                if(t < cost[i][0]) {
                    cost[i][0] = t;
                    from[i][0] = j;
                }
            }
        }

        if(i + 19 <= n) {
            for(int j = 1; j <= 27; ++j) {
                int t = 0;
                for (int k = 1; k <= N; ++k) {
                    t += diff[i+k-1][j][k];
                }
                if (t < cost[i][1]) {
                    cost[i][1] = t;
                    from[i][1] = j;
                }
            }
        }

        if (i + 20 <= n) {
            for (int j = 1; j <= 27; ++j) {
                int t = 0;
                for (int k=1; k <= N; ++k) {
                    t += diff[i + k - 1][j][k];
                }
                if (t < cost[i][2]) {
                    cost[i][2] = t,
                    from[i][2] = j;
                }
                for (int k = N; k; --k) {
                    t -= diff[i + k - 1][j][k];
                    t += diff[i + k][j][k];
                    if (t < cost[i][2]) {
                        cost[i][2] = t;
                        from[i][2] = j;
                    }
                }
            }
        }
    }
}

void calculate(int n) {
    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
    }

    for (int i = 19; i <= n; ++i) {
        int val = dp[i - 19] + cost[i - 18][0];
        if (dp[i] > val) {
            dp[i] = val;
            opt[i] = 19;
        }
        if (i >= 20) {
            val = dp[i - 20] + cost[i - 19][1];
            if (dp[i] > val) {
                dp[i] = val;
                opt[i] = 20;
            }
        }
        if (i >= 21) {
            val = dp[i - 21] + cost[i - 20][2];
            if (dp[i] > val) {
                dp[i] = val;
                opt[i] = 21;
            }
        }
    }
}

int main() {
    int n = 0, t = 0;

    readFont();
    fin >> n;
    readImages(n);
    preprocess(n);
    calculate(n);

    for(int i = n; i; i -= opt[i]) {
        ans[++t] = from[i - opt[i] + 1][opt[i] - 19];
    }

    for(int i = t; i; --i) {
        fout << ch[ans[i]];
    }
    fout << endl;
    return 0;
}