Problem: Example

Input

1 10 2
1 1 1


Output

2.0

Solution (in CPP):

Solution:

#include<bits/stdc++.h>
using namespace std;
#define D(x)    cout << #x " = " <<(x) << endl
#define MAX     1000
typedef long long int LL;

int k;
int cost[33];
const double INF = 1e100;

double solve(int n);
double dp[MAX+5][33], dp_solve[MAX+5];


double F(int n, int t){
    double ret = INF;
    if(t == 0){
        if(n == 1) return cost[0];
        return cost[0] + solve(n);
    }
    if(!n) return INF;

    if(dp[n][t] == dp[n][t]) return dp[n][t];

    for(int p1 = 1; p1 < n; p1++){
        double current = 0;
        current = ((n - p1) / (double) n) * F(n - p1, t - 1) + (p1 / (double) n) * (cost[t] + solve(p1));
        ret = min(ret, current);
    }

    return dp[n][t] = ret;
}

double solve(int n){
    if(n == 1) return 0;
    if(dp_solve[n] == dp_solve[n]) return dp_solve[n];

    double ret = numeric_limits<double>::max();
    for(int t = 1; t <= k; t++)
        ret = min(ret, F(n, t));

    return dp_solve[n] = ret;
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int st, ed, i, n;
    memset(dp, -1, sizeof(dp));
    memset(dp_solve, -1, sizeof(dp_solve));

    scanf("%d %d %d", &st, &ed, &k);
    for(i = 0; i <= k; i++) scanf("%d", &cost[i]);
    n = ed - st;


    printf("%0.10f\n", solve(n));
    return 0;
}