Submission #1985669

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

using int64 = long long;

const int MAX_W = 301;
const int MAX_H = 301;
const int64 INF = (1LL << 50);

char C[MAX_W][MAX_H];   // C[i][j] := 
int cost[MAX_W][MAX_H][MAX_H];
int64 dp[MAX_H][MAX_H];

int H, W;

int calc_cost(int id, int LH, int RH) {
    if (cost[id][LH][RH] >= 0) return cost[id][LH][RH];
    if (LH == 0 or RH == 0) return cost[id][LH][RH] = 0;
    // どっちも1より大きい
    int idxl = H - LH + 1;
    int idxr = H - RH + 1;
    return calc_cost(id, LH - 1, RH - 1) + (C[id][idxl] == C[id + 1][idxr]);
}

int main() {
    cin >> H >> W;

    for (int r = 0; r < H; r++) {
        string s;
        cin >> s;
        for (int c = 0; c < W; c++) C[c][H - r] = s[c];
    }

    memset(cost, -1, sizeof(cost));

    int64 ans = 0;
    for (int c = 0; c < W - 1; c++) {
        // dp
        fill((int64*)dp, (int64*)(dp + MAX_H), INF);

        dp[0][0] = 0;
        for (int LH = 0; LH <= H; LH++) {
            for (int RH = 0; RH <= H; RH++) {
                if (LH == 0 and RH == 0) continue;
                if (LH > 0) dp[LH][RH] = min(dp[LH][RH], dp[LH - 1][RH] + calc_cost(c, LH, RH));
                if (RH > 0) dp[LH][RH] = min(dp[LH][RH], dp[LH][RH - 1] + calc_cost(c, LH, RH));
            }
        }

        ans += dp[H][H];
        // cerr << "c: " << dp[H][H] << endl;
    }
    cout << ans << endl;

    /*
    cerr << "deg: " << calc_cost(1, 2, 2) << endl;
    cerr << "deg: " << calc_cost(1, 1, 1) << endl;
    */
    
    return 0;
}

Submission Info

Judge Result