OpTree

#include<stdio.h>
#include<algorithm>
using namespace std;

struct node{
    double freq;
    int num;
};

bool mycmp(node a,node b){
    return a.num < b.num;
}

node arr[1010];
double qs[1010];

double sum(int i,int j){
    return qs[j] - qs[i-1];
}

double dp[1010][1010];

double cal(int i,int j){
    if(j < i)return 0;
    if(j == i)return arr[i].freq;

    if(dp[i][j] != -1)return dp[i][j];
    double fsum = sum(i,j);

    double min = 1e9;

    for(int r = i ; r <= j ; r ++){
        double cost = cal(i,r-1) + cal(r+1,j);
        if(cost < min)min = cost;
    }
    return dp[i][j] = min + fsum;
}

int main(){
    for(int i = 0 ; i < 1010 ; i ++)for(int j = 0 ; j < 1010 ; j ++)dp[i][j] = -1;
    int n;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d",&arr[i].num);
    }
    for(int i = 1 ; i <= n ; i ++){
        scanf("%lf",&arr[i].freq);
    }
    sort(arr+1,arr+n+1,mycmp);
    for(int i = 1 ; i <= n ; i ++){
        qs[i] = qs[i-1] + arr[i].freq;
    }
    printf("%.4lf",cal(1,n));
    return 0;
}