#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<string> using namespace std; int n,j; float a[100],s,k1,c,f1[100],f[100][100][100];//定义为实数 int main() { cin>>n>>k1>>c; for (int i=1;i<=n;i++) { cin>>a[i]; s+=a[i]; } for (int i=1;i<=n;i++) f1[i]=a[i]/s;//因为概率是不变的,所以我们一开始就计算出各个点的概率 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int x=0;x<=n-1;x++) f[i][j][x]=210000000;//初始化 for (int i=1;i<=n+1;i++) for (int x=0;x<=n-1;x++) f[i][i][x]=(k1*(x+1)+c)*f1[i];//单单一个点为一棵树的时候先计算出值 for (int i=1;i<=n+1;i++) for (int x=0;x<=n;x++) f[i][i-1][x]=0;//指当我们在枚举区间时考虑把边界i或j当做根节点时,即没有左子树或右子树的时候,就会调用到f[i][i-1][x],因为没有所以值自然为0; for (int len=2;len<=n;len++)//枚举区间 for (int i=1;i<=n-len+1;i++) { j=i+len-1; for (int x=0;x<=n-1;x++) for (int k=i;k<=j;k++)//枚举区间内的根节点 { f[i][j][x]=min(f[i][j][x],f[i][k-1][x+1]+f[k+1][j][x+1]+(k1*(x+1)+c)*f1[k]);//两边的加上本身的; } } printf("%.3f",f[1][n][0]);//保留三位小数输出 return 0; }
原文:http://www.cnblogs.com/2014nhc/p/6246917.html