Submission #2302460

---

Source Code Expand

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

int N;
vector<vector<bool>> if_palindrome; // [left, right]
vector<int> costs;

int dp[5000];

int split(int now){
    if(now == N){
        return 0;
    }else if(dp[now] != -1){
        return dp[now];
    }else{
        int ans = 1e9;
        for(int i = 1; now + i <= N; i++){
            if(if_palindrome[now][now + i - 1]){
                ans = min(ans, costs[i - 1] + split(now + i));
            }
        }
        return dp[now] = ans;
    }
}

int main(){
    string S;
    cin >> N >> S;
    costs.resize(N);
    for(int i = 0; i < N; i++){
        cin >> costs[i];
    }
    if_palindrome.resize(N);
    for(int i = 0; i < N; i++){
        if_palindrome[i].resize(N);
        for(int j = 0; j < N; j++){
            if_palindrome[i][j] = false;
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; i - j >= 0 && i + j < N; j++){
            if(S[i - j] != S[i + j]){
                break;
            }
            if_palindrome[i - j][i + j] = true;
        }
    }
    for(int i = 0; i < N - 1; i++){
        for(int j = 0; i - j >= 0 && i + j + 1 < N; j++){
            if(S[i - j] != S[i + j + 1]){
                break;
            }
            if_palindrome[i - j][i + j + 1] = true;
        }
    }
    fill(dp, dp + 5000, -1);
    cout << split(0) << endl;
}

Submission Info

Judge Result