Ztc不愿意来回走，所以合并只能在相邻的两堆书间进行。书本合并前后，位置不变

就这两句就已经限定了要么从头和合并书堆！要么从末尾合并！因为他不愿意来回走！所以我认为应该没最优解！问题的结果在你输入书堆的数据时已经定好了！就是一个循环解题的过程！这就是我的一点见解！不知对否！

基本的算法思路是反复循环找费力最少的两堆合并，直到剩下一堆！

我的思路可以解决前两个样例（每次合并费力最少的只有唯一一个），但是最后一个样例（每次费力最少的不是唯一一个，并且是相邻的两组费力均为最小值）的情况我还没考虑好应该怎么处理！！

暂时的代码贴出来（在楼主代码基础上增加的我的思路）：

#include <stdio.h>
#define MAXL 400 //定义最大测资为400
struct book
{
    long int w,v;//每一堆的书本都有重量W和价值V
}book[MAXL];
//公式：合并i,j两堆书本所需要的力气为Wi-Vi+Wj-Vj。
long int strength=0,w_count,v_count=0;//strength为总合并重量，w_count为临时的w和变量，v_count为v和的临时变量
void print()//打印结果
{
    printf("%ld\n",strength);
}
int current_merger(int i) //判断当前应该首先合并哪两堆，返回两堆中的前一堆编号
{
    int j,min_strength=book[0].w-book[0].v+book[1].w-book[1].v;
    int t=0;
    for(j=1;j<=i;j++)
        if(min_strength > book[j].w-book[j].v+book[j+1].w-book[j+1].v)
            t=j,min_strength = book[j].w-book[j].v+book[j+1].w-book[j+1].v;
    return t;
}
int merge(int t,int end)   //合并 t t+1 两堆，并且其后的前移
{
    int i;
    strength = strength + book[t].w-book[t].v+book[t+1].w-book[t+1].v;
    book[t].w+=book[t+1].w;
    book[t].v+=book[t+1].v;

    for(i=t+1;i<=end;i++)
    {
        book[i].w = book[i+1].w;
        book[i].v = book[i+1].v;       
    }
    return 0;
}

void sorting_book(int n)
{
    int i,t;
    for(i=n-2;i>=0;i--)//循环n-1次,即合并n-1次,最后变成一堆
    {  
        t=current_merger(i);
        merge(t,i);
    }
}
main()
{
    int n,i;//n为有几堆书本
    scanf("%d",&n);//输入有几堆书本
    for(i=0;i<n;i++)//输入N堆书
    scanf("%d %d",&book[i].w,&book[i].v);//用户输入数据
    sorting_book(n);//将数据传入sorting_book中  
    print();//打印结果函数
}

[ 本帖最后由 jack10141 于 2010-9-20 23:57 编辑 ]

Ztc不愿意来回走，所以合并只能在相邻的两堆书间进行。

这句话的理解应该是合并应该在相邻的两堆书中进行，（Ztc不愿意搬着书来回走，但是如果空着手，还是很乐意的！）所以，他只合并相邻的书堆。。。。。。
如果不是这样来理解，此题无解！大家可以来讨论下！！

LZ 还有没别的样例？多发几个过来，我测试下我的代码！！

我需要的是有标准答案的那种！！

[ 本帖最后由 jack10141 于 2010-9-20 22:41 编辑 ]

还有 我发现一个问题，本问题应该有这样的限制：
【输 入】
输入文件book.in的第一行是一个整数n(2≤n≤400)。
第二行到第n+1行每行两个整数w和v(0<v<w≤1000)。

但是你100行的样例中有这样不符合这个限制的数据：

...
9 12
5 999
...

是不是要么从头开始合并,要么从尾巴开始合并?
如果是这样就简单多了!不知道理解的对不对

你算一下如果从尾部开始合并是不是测试数据标准答案!

你说的这样肯定不对了！！！！

Ztc不愿意来回走，所以合并只能在相邻的两堆书间进行。

这句话的理解应该是合并应该在相邻的两堆书中进行，（Ztc不愿意搬着书来回走，但是如果空着手，还是很乐意的！）所以，他只合并相邻的书堆。。。。。。

不一定从尾或者从头
任何位置都可以

题目的意思是可以合并任意相临的两堆,其余未合并的顺序不变啊!!
合并了一堆后,接下来要合并的位置跟之前在哪里合并的没关系!依然可以合并任意相临的两堆!

如果只是找到一个合并的起始位置,然后向左或向右合并,那就把问题改变了!!!

[ 本帖最后由 jack10141 于 2010-9-21 15:13 编辑 ]