codevs 1048/洛谷 1880:石子归并

题目描述 Description

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n（n<=100）

第二行n个整数w1,w2...wn (wi <= 100)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4 1 1 4

样例输出 Sample Output

　　芒果君：这是我博客的第一道题啊~是一道DP啊~其实刚看到的时候有点懵，然后又看了一本通上的代码，果然，我并没有恍然大悟OTZ 用f[i][j]表示从第i个到第j个的最小合并代价，状态转移方程是，f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]),就是判断原来的方案和你枚举的新的两端合并起来哪个更小。然后这道题也告诉我memset新的用法……

#include<cstdio>

#include<cstring>

using namespace std;

int f[][],s[],n,i,j,k,x;

int min(int a,int b)

{

    return a<b?a:b;

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&x);

        s[i]=s[i-]+x;//求前缀和

    }

    memset(f,/,sizeof(f));//把每一位都赋予一个很大的整数

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

    {

        f[i][i]=;//自己合并自己花费是0

    }

    for(i=n-;i>=;--i)//合并2个、合并3个……合并n个

    {

        for(j=i+;j<=n;++j)//枚举长度

        {

            for(k=i;k<=j-;++k)//把这个长度里划成两段

            {

                f[i][j]=min(f[i][j],f[i][k]+f[k+][j]+s[j]-s[i-]);

            }

        }

    }

    printf("%d",f[][n]);

    return ;

}

　　然后这道题还有一个升级版，就是洛谷的1880，只不过把这个链状的变成了环状的，最大值和最小值都要求，我就稍微改了一下，比如第一次做“1 2 3 4 5”，第二次做“2 3 4 5 1”，第五次做“5 1 2 3 4”，这样就解决问题了。

#include<cstdio>

#include<cstring>

using namespace std;

int f1[][],f2[][],a[],s[],n,i,j,k,t,x,MIN=<<,MAX;

int min(int a,int b)

{

    return a<b?a:b;

}

int max(int a,int b)

{

    return a>b?a:b;

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&a[i]);

    }

    for(t=;t<=n;++t)

    {

        for(i=;i<t;++i)

        {

            s[i]=s[i-]+a[n+i-t+];

        }

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

        {

            s[i]=s[i-]+a[i-t+];

        }

        memset(f1,/,sizeof(f1));

        memset(f2,,sizeof(f2));

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

        {

            f1[i][i]=;

            f2[i][i]=;

        }

        for(i=n-;i>=;--i)

        {

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

            {

                for(k=i;k<=j-;++k)

                {

                    f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+][j]+s[j]-s[i-]);

                    f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+][j]+s[j]-s[i-]);

                }

            }

        }

        MIN=min(f1[][n],MIN);

        MAX=max(f2[][n],MAX);

    }

    printf("%d\n%d\n",MIN,MAX);

    return ;

}

巴特西

codevs 1048/洛谷 1880:石子归并

最新文章

热门文章