BZOJ1261: [SCOI2006]zh_tree

#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;
}