Submission #6001579

---

Source Code Expand

#include <iostream>

using namespace std;

long dp[301][301];
long dbl[301][301];

void clear(){
    for(int i = 0; i <= 300; i++){
        for(int j = 0; j <= 300; j++){
            dp[i][j] = 0;
            dbl[i][j] = 0;
        }
    }
}

int main(){
    long ans = 0;
    int H, W;
    cin >> H >> W;
    char c[300][300];
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> c[i][j];
        }
    }
    for(int j = 0; j < W-1; j++){
        clear();
        for(int i = 0; i <= H; i++) {
            dp[0][i] = 0;
            dp[i][0] = 0;
            dbl[i][0] = 0;
            dbl[0][i] = 0;
        }
        for(int i = 1; i <= H; i++){
            for(int k = 1; k <= H; k++){
                if(c[i-1][j] == c[k-1][j+1]){
                    dbl[i][k] = dbl[i-1][k-1]+1;
                }else{
                    dbl[i][k] = dbl[i-1][k-1];
                }
                dp[i][k] = min(dp[i-1][k], dp[i][k-1])+dbl[i][k];
            }
            ans += dp[H][H];
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result