ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int inf=2*1e9+1;
int n;
vi a,b;
vi s;
vvi dp;
int f(int l,int r){
return s[r]-s[l];
}
int main(){
cin>>n;
a=b=vi(n);
s=vi(n+1);
dp=vvi(n,vi(n+1));
for(int i=0;i<n;i++){
cin>>a[i];
s[i+1]=s[i]+a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
dp[i][i+1]=b[i];
}
for(int i=2;i<=n;i++) for(int j=0;j+i<=n;j++){
int res=inf;
for(int k=j;k<i+j;k++){
res=min(res,(f(j,k)<f(k+1,i+j)?dp[k+1][i+j]:dp[j][k])+b[k]);
}
dp[j][i+j]=res;
}
cout<<dp[0][n]<<endl;
}