Indeedなう本戦B C問題 Palindrome Concatenation

ある文字列を作るために回文を組み合わせるのだが、その回文の長さに応じてコストがあり、そのうちで最小コストの組み合わせをもとめる問題。

普通にやるとdpでO(N^3)。
その文字列が回文であるかどうかを判定するテーブルを、文字列のcenterから広げていくやり方をとればO(N^2)でテーブルが作成できるので、最終的にO(N^2)で間に合う…。
バグらせまくって辛かった…。iとかjが何baseのindexなのかメモるなり統一するなりした方がいいですね。

    int N; cin >> N;
    string S; cin >> S;
    int C[N];
    rep(i, N) cin >> C[i];

    bool IS[N][N];
    memset(IS, false, sizeof(IS));
    for(int center=0; center<N; center++){
        int L = center, R = center;
        while(L >= 0 && R < N && S[L] == S[R]){
            IS[L][R] = true;
            L--; R++;
        }
        L = center, R = center+1;
        while(L >= 0 && R < N && S[L] == S[R]){
            IS[L][R] = true;
            L--; R++;
        }
    }

    int dp[N+1];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i=1; i<=N; i++){
        for(int j=0; j<i; j++){
            if(IS[j][i-1] && (dp[i] == -1 || dp[i] > dp[j]+C[i-j-1])){
                dp[i] = dp[j] + C[i-j-1];
            }
        }
    }
    cout << dp[N] << endl;