题目里讲的是归并。  用递归做

[ 本帖最后由 sunyh1999 于 2010-9-24 07:55 编辑 ]

最新的代码我贴出来（用最小代价子母树的解题思路，没有考虑优化），目前所有的样例测试都没有问题！

#include <stdio.h>
#define MAXL 400 //定义最大测资为400
int book[MAXL];
int f[MAXL][MAXL];  //f[i][j] (i<=j) 存放i~j合并为一堆的最小力气花费，若i>j,则为-1

long int strength=0;  //strength为总合并重量
void print()//打印结果
{
    printf("%ld\n",strength);
}

int sum(int start,int end)        //计算从起点到终点的累加和
{
    int i,s=0;
    for(i=start;i<=end;i++)
    {
        s+= book[i];
    }
    return s;
}
int min_strength(int s, int e)    //求从s开始到e结束合并为一堆的最小力气花费
{
    int i,j,k,min=99999999;        //min 存放最小值，初始其为一个很大的数，可以改为int类型的最大数
    if(s==e)                    //起点和终点为一个点
        return 0;
    if(s==e-1)                    //起点和终点相邻
    {
        f[s][e]=sum(s,e);        //写入f数组
        return f[s][e];            //返回
    }
    if(f[s][e] != -1)            //不等于-1表示之前已经计算过！所以直接返回
    {
        return f[s][e];
    }
    for(k=s;k<e;k++)            //以前没有计算过，那么递归计算，找最小值！
    {  
        if( min  >  min_strength(s, k) +  min_strength(k+1, e)  )
            min  =  min_strength(s, k) +  min_strength(k+1, e)  ;
    }
    min = min + sum(s,e);
    f[s][e]=min;
    return min;
}
main()
{
    int n,i,j,w,v=0;//n为有几堆书本
    scanf("%d",&n);//输入有几堆书本
    for(i=0;i<n;i++)//输入N堆书
    {
        scanf("%d %d",&w,&v);//用户输入数据
        book[i]=w-v;
    }
    for(i=0;i<n;i++)        //f数组所有元素都赋值-1
        for(j=0;j<n;j++)
            f[i][j]=-1;
    for(i=0;i<n;i++)        //对角线元素为0
        f[i][i]=0;
    strength=min_strength(0,n-1);//求最小力气！  
    print();//打印结果函数
}

 

[ 本帖最后由 jack10141 于 2010-9-24 10:46 编辑 ]

版主大人，要不建一个群，这样讨论起来要方便些。
我的QQ 693025091 ，以后有问题要讨论算我一个。

好啊，你开个群吧！

貌似是简单的动态规划题目
楼主可以百度一下 石子合并题解
我dp掌握的不好,所以无法解释清楚
题目差不多!

本想写了个测试数据，可是遇到错误，各位看看：



#include <stdio.h>
#include <stdlib.h>
#define MAXL 400 //定义最大测资为400
int book[MAXL];
int f[MAXL][MAXL];  //f[i][j] (i<=j) 存放i~j合并为一堆的最小力气花费，若i>j,则为-1
FILE *finput,*foutput;
long int strength=0;  //strength为总合并重量
void file_start()
{
    finput=fopen("book.in","r");
    foutput=fopen("book.out","w");
    if(finput==NULL)
        exit(0);
}
void print()//打印结果
{
    fprintf(foutput,"%ld\n",strength);
    system("pause");
}
int sum(int start,int end)        //计算从起点到终点的累加和
{
    int i,s=0;
    for(i=start;i<=end;i++)
    {
        s+= book[i];
    }
    return s;
}
int min_strength(int s, int e)    //求从s开始到e结束合并为一堆的最小力气花费
{
    int k,min=99999999;        //min 存放最小值，初始其为一个很大的数，可以改为int类型的最大数
    if(s==e)                    //起点和终点为一个点
        return 0;
    if(s==e-1)                    //起点和终点相邻
    {
        f[s][e]=sum(s,e);        //写入f数组
        return f[s][e];            //返回
    }
    if(f[s][e] != -1)            //不等于-1表示之前已经计算过！所以直接返回
    {
        return f[s][e];
    }
    for(k=s;k<e;k++)            //以前没有计算过，那么递归计算，找最小值！
    {  
        if( min  >  min_strength(s, k) +  min_strength(k+1, e)  )
            min  =  min_strength(s, k) +  min_strength(k+1, e)  ;
    }
    min = min + sum(s,e);
    f[s][e]=min;
    return min;
}
main()
{
    int n,i,j,w,v=0;//n为有几堆书本
    fscanf(finput,"%d",&n);//输入有几堆书本
    file_start();
    for(i=0;i<n;i++)//输入N堆书
    {
        fscanf(finput,"%d %d",&w,&v);//用户输入数据
        book[i]=w-v;
    }
    for(i=0;i<n;i++)        //f数组所有元素都赋值-1
        for(j=0;j<n;j++)
            f[i][j]=-1;
    for(i=0;i<n;i++)        //对角线元素为0
        f[i][i]=0;
    strength=min_strength(0,n-1);//求最小力气！  
    print();//打印结果函数
    fclose(finput);
    fclose(foutput);
}

C语言讨论新群（群名：C）
群号：87701413

欢迎对C语言有兴趣的人加入！！

版主大人，您来做管理员。

楼主打算从文件输入，然后输出到文件？那你的文件什么时间打开和关闭的？？

递归呀递归  好东西

file_start开始初始文件，fin表示输入，fout表示输出。