bzoj 1261 区间DP

　　首先我们知道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=;

    for (int i=;i<=n;i++) scanf("%lf",&p[i]),s+=p[i];

    for (int i=;i<=n;i++) p[i]/=s;

    //for (int i=1;i<=n;i++) printf("%0.3f ",p[i]); printf("\n");

    for (int i=;i<=n;i++) ans+=p[i]*(k+c);

    //printf("%0.3f\n",ans);

    for (int i=;i<=n;i++) p[i]+=p[i-];

    for (int i=;i<=n;i++)

        for (int j=i+;j<=n;j++) w[i][j]=inf;

    for (int l=;l<=n;l++)

        for (int i=;i<=n-l+;i++)

        {

            int j=i+l-;

            //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-]+p[k-]-p[i-]+w[k+][j]+p[j]-p[k]);

                //printf("%d %0.3f \n",k,w[i][j]);

            }

            //printf("%0.3f\n",w[i][j]);

        }

    ans+=w[][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 ;

}

巴特西

bzoj 1261 区间DP

最新文章

热门文章