Problem: Example

Input

1 10 2
1 1 1


Output

2.0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1005
#define SIZE 31

int R_OK,R_FALSE,K;
double cost[SIZE];
double dp[SIZE][NUM];
double memo[NUM];


double recursive(int length){

	if(memo[length] != DBL_MAX){
		return memo[length];
	}

	for(int x = 1; x <= min(K,length); x++){

		if(x == 1){

			for(int start = 1; start <= length-1; start++){

				dp[x][length] = min(dp[x][length],(double)start/(double)length*(recursive(start)+cost[1])+
						(double)(length-start)/(double)length*(recursive(length-start)+cost[0]));
			}

		}else{

			for(int start = 1; start <= length-x; start++){

				dp[x][length] = min(dp[x][length],(double)start/(double)length*(recursive(start)+cost[x])+
						(double)(length-start)/(double)length*dp[x-1][length-start]);
			}
		}
		memo[length] = min(memo[length],dp[x][length]);
	}

	return memo[length];
}

int main(){

	scanf("%d %d %d",&R_OK,&R_FALSE,&K);

	int max_index = R_FALSE-R_OK;

	for(int i = 0; i <= K; i++){
		scanf("%lf",&cost[i]);
	}

	for(int i = 0; i <= min(K,max_index); i++){
		for(int k = 0; k <= max_index; k++){
 			dp[i][k] = DBL_MAX;
		}
	}

	for(int i = 0; i <= max_index; i++)memo[i] = DBL_MAX;

	memo[0] = 0;
	memo[1] = 0;
	memo[2] = (cost[0]+cost[1])/2.0;
	dp[1][2] = memo[2];

	printf("%.10lf\n",recursive(max_index));

	return 0;
}