SMMR-156: OpTree

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pii = pair<int,double>;
double qs[1010];
pii ar[1010];
int n;
double dp[1010][1010];
bool compare(pii a,pii b){
    return a.first < b.first;
}
int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&ar[i].first);
    for(int i=1;i<=n;i++){
        scanf("%lf",&ar[i].second);
        dp[n+1][i]=0.0;
        dp[i][0]=0.0;
        for(int j=1;j<=n;j++) {
            dp[i][j]=(double)INF;
            if(i>j) dp[i][j]=0.0;
        }
    }
    sort(ar+1,ar+n+1,compare);//sort ar[1] to ar[n]
    for(int i=1;i<=n;i++)
        qs[i]=qs[i-1]+ar[i].second;

    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            if(i==j){
                dp[i][j]=ar[i].second;
                continue;
            }
            double sub=qs[j]-qs[i-1];
            for(int k=i;k<=j;k++){
                dp[i][j] = min(dp[i][j],(double)(dp[i][k-1]+dp[k+1][j]));
            }
            dp[i][j]+=sub;
        }
    }

    printf("%.4f",dp[1][n]);


    return 0;
}
/*
3
10 12 20
34 8 50
*/