首先我们知道ans=Σ(h[i]*f[i])=Σ(h[i]*d[i])/s=Σ(k(r[i]+1)+c)*d[i]/s=Σ(k*r[i]+(k+c))*d[i]/s
我们可以发现，除了k*r[i]之外，剩下的都是常数，那么我们这道题就转化成了求k*r[i]的最小值，那么区间dp就可以了，对于区间i,j，每次选取一个k为根，由左右两个区间转移过来，相当于将左右子树所有的深度+1，那么增加的代价就为两区间和，这样转移就可以了。
对于第二问我们可以在转移的时候记录每个区间的最优决策点，也即选取的根，那么最后递归生成遍历就行了，但是bz上没有第二问，不用输出。
反思：带错数据，将自己造的一组数据当成样例，查了半天错。
/************************************************************** Problem: 1261 User: BLADEVIL Language: C++ Result: Accepted Time:0 ms Memory:824 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #define maxn 40 #define inf 1<<30 using namespace std; int n; double ans,k,c; double p[maxn],w[maxn][maxn]; int root[maxn][maxn]; void getmin(double &x,double y) {x=(y<x)?y:x;} int main() { scanf("%d%lf%lf",&n,&k,&c); double s=0; for (int i=1;i<=n;i++) scanf("%lf",&p[i]),s+=p[i]; for (int i=1;i<=n;i++) p[i]/=s; //for (int i=1;i<=n;i++) printf("%0.3f ",p[i]); printf("\n"); for (int i=1;i<=n;i++) ans+=p[i]*(k+c); //printf("%0.3f\n",ans); for (int i=1;i<=n;i++) p[i]+=p[i-1]; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) w[i][j]=inf; for (int l=2;l<=n;l++) for (int i=1;i<=n-l+1;i++) { int j=i+l-1; //printf("%d %d %0.3f\n",i,j,w[i][j]); for (int k=i;k<=j;k++) { getmin(w[i][j],w[i][k-1]+p[k-1]-p[i-1]+w[k+1][j]+p[j]-p[k]); //printf("%d %0.3f \n",k,w[i][j]); } //printf("%0.3f\n",w[i][j]); } ans+=w[1][n]*k; printf("%0.3f\n",ans); /* for (int i=1;i<=n;i++) { for (int j=1;j<=i;j++) printf("%0.3f ",w[j][i]); printf("\n"); } */ return 0; }
原文：http://www.cnblogs.com/BLADEVIL/p/3555494.html