ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
const int inf=2*1e9+1;
template <class T>
class RMQ{
private:
int n;
vector<T> rmq;
T Query_func(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return inf;
if(a<=l&&r<=b) return rmq[k];
int m=(l+r)/2;
return min(Query_func(a,b,k*2+1,l,m),Query_func(a,b,k*2+2,m,r));
}
public:
void Init(int n_){
n=1;
while(n<n_) n*=2;
rmq=vector<T>(2*n-1,inf);
}
void Update(int k,T x){
k+=n-1;
rmq[k]=x;
while(k>0){
k=(k-1)/2;
rmq[k]=min(rmq[k*2+1],rmq[k*2+2]);
}
}
T Query(int a,int b){
return Query_func(a,b,0,0,n);
}
T Open(int k){
return rmq[n+k-1];
}
};
int n;
vi a,b;
vi s;
vector<RMQ<int> > dpl,dpr;
int f(int l,int r){
return s[r]-s[l];
}
int main(){
scanf("%d",&n);
a=b=vi(n);
s=vi(n+1);
dpl=dpr=vector<RMQ<int> >(n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
s[i+1]+=s[i]+a[i];
dpl[i].Init(n+1);
dpr[i].Init(n+1);
}
for(int i=0;i<n;i++) scanf("%d",&b[i]);
for(int i=0;i<n;i++){
dpl[i].Update(i+1,b[i]+(i+1<n?b[i+1]:0));
if(i) dpr[i].Update(i-1,b[i]+b[i-1]);
}
for(int i=1;i<n;i++) for(int j=0;j+i<n;j++){
int l=j,r=j+i+1,res;
while(r-l>1){
int m=(l+r)/2;
if(f(j,m)<f(m+1,i+j+1)) l=m;
else r=m;
}
res=min(dpl[j].Query(r,i+j+1),dpr[i+j].Query(j,r));
dpl[j].Update(j+i+1,res+(j+i+1<n?b[j+i+1]:0));
if(j) dpr[j+i].Update(j-1,res+b[j-1]);
}
printf("%d\n",dpl[0].Open(n));
}