石子合并

2013年11月29日5,3710

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1295

[问题描述]
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小总得分。

[编程任务]
对于给定n堆石子,编程计算合并成一堆的最小总得分。

[输入格式]
输入文件的第1 行是正整数n，1<=n<=1000，表示有n堆石子。
第2行为n个整数，分别表示每堆石子的个数。

[输出格式]
对于每组输入数据，输出一行，为最小总得分。

输入输出样例：

输入unite.in	输出unite.out
4 4 　4　5　9	43

代码

#include<iostream>
#include<cstring>
using namespace std;
int f[1001][1001];
int s[1001];
int n,i,j,k,l,x;
int mn=0x7fffffff;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        s[i]=s[i-1]+x;
    }
    for(i=n+1;i<=2*n;i++){
       s[i]=s[i-n]+s[n];}
    memset(f,127/3,sizeof(f));
    for(i=1;i<=2*n;i++)f[i][i]=0;
    for(l=1;l<=n;l++)
        for(i=1;i<=2*n-l;i++)
        {
            j=i+l;
            for(int k=i;k<j;k++)
                f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1],f[i][j]);
        }
    for(i=1;i<=n;i++)
        mn=min(mn,f[i][i+n-1]);
             cout<<mn;
    return 0; 
}

#include<iostream>

#include<cstring>

using namespace std;

int f[1001][1001];

int s[1001];

int n,i,j,k,l,x;

int mn=0x7fffffff;

int main()

{

cin>>n;

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

{

cin>>x;

s[i]=s[i-1]+x;

}

for(i=n+1;i<=2*n;i++){

s[i]=s[i-n]+s[n];}

memset(f,127/3,sizeof(f));

for(i=1;i<=2*n;i++)f[i][i]=0;

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

for(i=1;i<=2*n-l;i++)

{

j=i+l;

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

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

}

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

mn=min(mn,f[i][i+n-1]);

cout<<mn;

return 0;

}

« 「JoyOI1055」沙子合并「vijos1057」盖房子 »

hzwer.com _ Home | http://hzwer.com

石子合并

分类目录

热门文章

Myfriends

近期评论