F 竹摇清风拂面

F题跟多边形三角剖分很像，而且根据数据范围，很像区间DP的题目，故考虑区间DP。

题解以及大多数人的做法都是扩大两倍数值跑迭代式（循环）动规，这里提供一种记忆化搜索的方式，同时不需要扩大数组两倍。

用f[l][r]表示区间 ，从 顺时针指向 的最小代价。对于每个区间 可以通过再枚举一个点 ，从而将区间划分为 以及 ,即有 f[l][r] = min(f[l][r],a[l]*a[i]+dfs(l,i-1)+dfs(i+1,r);

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 510;
int a[N], n;
int f[N][N];
string s;
int dfs(int l, int r) {
    if (l > r) return 0;
    if ((r - l + 1) % 2) return 1e18;
    if (f[l][r] != -1) return f[l][r];
    f[l][r] = 1e18;
    for (int i = l + 1; i <= r; i++) {
        if (s[l] == s[i])
            f[l][r] = min(f[l][r], a[l] * a[i] + dfs(l + 1, i - 1) + dfs(i + 1, r));
    }
    return f[l][r];
}
void solve() {
    cin >> n;
    cin >> s;
    memset(f, -1, sizeof f);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = dfs(0, n - 1);
    if (ans >= 1e18) {
        ans = -1;
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}