JOISCO 2022 2A

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC target("avx,avx2")

constexpr int INF = (int)2e18;
constexpr int N = (int)3000 + 11;
constexpr int MAXN = (int)1e5 + 11;
constexpr int md[2] = {(int)1e9+7,(int)1e9+9};
constexpr int p[2] = {(int)101,103};

mt19937 rnd(time(nullptr));

int dp[N][N];
int A,B,C;
int h[2][N];
int P[2][N];

int getHash(int l,int r,int t){
    int h1 = h[t][r];
    if(l)
        h1 = (h1 - h[t][l-1]);
    if(h1 < 0)
        h1 += md[t];
    return h1;
}

bool compareOne(int l1,int r1,int l2,int r2,int t){
    if(r2 < r1){
        swap(l1,l2);
        swap(r1,r2);
    }
    int h1 = getHash(l1,r1,t);
    int h2 = getHash(l2,r2,t);
    h1 = (h1 * P[t][r2-r1]) % md[t];
    return h1 == h2;
}

bool compare(int l1,int r1,int l2,int r2){
    bool ok = true;
    for(int i = 0; i < 1; i++)
        ok &= compareOne(l1,r1,l2,r2,0);
    return ok;
}

void solve(){
    int n;
    cin >> n;

    P[0][0] = P[1][0] = 1;
    for(int i = 1; i < N; i++){
        for(int j = 0; j < 2; j++)
            P[j][i] = (P[j][i-1] * p[j]) % md[j];
    }

    string s;
    cin >> s;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            h[j][i] = P[j][i] * s[i];
            if(i)
                h[j][i] = (h[j][i] + h[j][i-1]) % md[j];
        }
    }

    cin >> A >> B >> C;

//    int d[N];
//    for(int i = 0; i < N; i++)
//        d[i] = INF;
//    d[0] = 0;
//    for(int i = 1; i < N; i++){
//        d[i] = min(d[i],d[i-1]+A);
//        for(int j = i + i, c = 2; j < N; j += i,c++)
//            d[j] = min(d[j],d[i]+B+c*C);
//    }
//
//    cout << d[s.size()];
//    return;

    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            dp[i][j] = (j-i+1)*A;
        }
    }

    for(int len = 1; len <= n; len++){
        for(int i = 0; i + len - 1 < n; i++){
            int j = i+len-1;

            for(int k = i; k <= j; k++){
                dp[i][j] = min(dp[i][j],dp[k][j]+(k-i)*A);
                dp[i][j] = min(dp[i][j],dp[i][k]+(j-k)*A);
            }
            int cur = dp[i][j]+B+C;
            int pr = j;
            for(int t = j+1; t < n;){
                cur += A;
                if(t - len + 1 > pr && compare(i,j,t-len+1,t)){
                    cur = cur - len * A + C;
                    pr = t;
                }
                dp[i][t] = min(dp[i][t],cur);
                t++;
            }
        }
    }

//    cerr << "DEBUG " << dp[2][3] << "\n";
//    cout << dp[0][2] << "\n";

    cout << dp[0][n-1];

    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    while(tests--){
        solve();
    }
}
/**
18
aababbbababbbaabbb
10000
1
100


aaaaaa


**/