AC

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

int main() {
int n;
cin >> n;
vector<int> a(n + 2), b(n + 2);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];

// dp[i][j] 表示消灭区间 [i, j] 的最小伤害
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

for (int len = 1; len <= n; ++len) {
    for (int i = 1; i + len - 1 <= n; ++i) {
        int j = i + len - 1;
        if (i == j) {
            dp[i][j] = a[i] + b[i - 1] + b[i + 1];
        } else {
            dp[i][j] = INT_MAX;
            for (int k = i; k <= j; ++k) {
                int cost = a[k] + b[i - 1] + b[j + 1];
                int left = (k > i) ? dp[i][k - 1] : 0;
                int right = (k < j) ? dp[k + 1][j] : 0;
                dp[i][j] = min(dp[i][j], left + right + cost);
            }
        }
    }
}

cout << dp[1][n] << endl;
return 0;

}