区间dp, 非记忆化搜索解法 | #竹摇清风拂面#

区间标准解法

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 510, MOD = 998244353;
const LL INF = 1e18;

int n;
string s;
LL a[N];

void solve() {
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<vector<LL>> f(n + 2, vector<LL>(n + 2, INF));
    for (int i = 1; i <= n + 1; ++i) {
        f[i][i - 1] = 0;
    }

    for (int len = 2; len <= n; len += 2) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            for (int k = i + 1; k <= j; k += 2) {
                if (s[i] == s[k]) {

                    if (f[i + 1][k - 1] != INF && f[k + 1][j] != INF) {
                        LL v = f[i + 1][k - 1] + f[k + 1][j] + a[i] * a[k];
                        if (v < f[i][j]) f[i][j] = v;
                    }
                }
            }
        }
    }

    if (f[1][n] == INF) f[1][n] = -1;
    cout << f[1][n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}