https://ac.nowcoder.com/acm/problem/210807

刷野

区间dp：定义状态dp[i][j]表示消灭i到j怪物得最小值。第一维枚举区间长度
第二维枚举区间左端点，有了长度相应得右端点也出现，第三位枚举最后消灭哪只怪兽。
状态转移为:dp[i][j] = max(dp[i][j] , dp[i][m-1] + dp[m+1][j] + a[m] + b[i-1] + b[j+1])
注意边界得处理和初始化

#include <bits/stdc++.h>
typedef  long long ll ;
#define int ll
using namespace std ;
typedef pair<int,int> pii;
int quickpow(int a,int b,int mo){int s;for(s=1;b;b>>= 1,a=a*a%mo)if(b&1)s=s*a%mo;return s;}
#define INF 0x3f3f3f3f
const double PI = acos(-1.0);
const int maxn = 5e2+9;
const int N = 1e4+9;
const int mod = 9901;
int dp[maxn][maxn];
int a[maxn];
int b[maxn];
void Solve(){
    int n ;
    cin >> n ;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> b[i];
    }
    a[0] = a[n+1] = b[0] = b[n+1] = 0 ;
    for(int i = 1 ; i <= 500 ; i++){
        for(int j = 1 ; j <= 500 ; j++){
            if(j < i) dp[i][j] = 0 ;
            else dp[i][j] = INF;
        }
    }
    for(int i = 1 ; i <= n ; i++){
        dp[i][i] = a[i] + b[i-1] + b[i+1];
    }
    for(int len = 2 ; len <= n ; len++){
        for(int i = 1 ; i + len - 1 <= n ; i++){
            int j = i + len - 1;
            for(int m = i ; m <= j ; m++){
                dp[i][j] = min(dp[i][j] , dp[i][m-1] + dp[m+1][j] + a[m] + b[i-1] + b[j+1]);
            }
        }
    }
    cout << dp[1][n] << endl;

}
//9043

signed main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("D:\\c++\\in.txt", "r", stdin);
        //freopen("D:\\c++\\out.txt", "w", stdout);
    #endif
        Solve();
}