Dzx从日本回来了，并为TN准备了礼物----一个恐龙模型。TN想把它尽快拼好，但是由于模型很庞大，TN又实在比较懒，所以他希望你为他寻找一个最节省时间的拼装方案。

模型是由N个零件组成的，每次TN可以选取两个零件拼装在一起来组成一个新的零件，直到得到完整的模型。由于零件的复杂程度不同，TN每次拼装所需要的时间也是不同的，对于两个零件A和B，假设他们的复杂程度分别为a和b，则TN要将这两个零件拼装在一起所需要的时间为a+b，而这由两个零件所组成的新零件的复杂程度为a+b。

现在TN已经统计出了每个零件的复杂程度，你能告诉他最快的拼装方发需要多少时间么？

输入
Line 1： N (1 <= N <= 10000)，零件数目
Line 2： N Integers，表示每个零件的复杂程度
输出
最快的拼装方案所需要的时间
样例输入
3
1 2 9样例输出
15

这道题谁能给个算法和思路~不胜感激~
   

这是个数字重复利用的问题 就是数字大的用的越少 越快

所以你开始对样式时间进行排序
最小的两个第一次拼装 得到一个新的数
把这个数放到数列里 再排序

每次都用最小的两个拼装 ！

好的谢谢~我待会去试试看~

我编好了~不过在poj（2994）刷的时候超时了````您看看这程序哪里可以优化算法么？我是大一新生~望多指教~

#include<stdio.h>
#include<stdlib.h>
#include<memory>
#include<math.h>

int count;

int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;
}


void func(int a[], int x, int n)    {
    if(x == n + 1)
        return;
    qsort(a + x - 1, n - x + 2, sizeof(a[0]), cmp);
    count += a[x - 1] + a[x];
    a[x] += a[x - 1];
    func(a, x + 1, n);
    return;
}


int main()    {
    int i, n, a[10010];
    memset(a, 0, sizeof(a));              

    scanf("%d", &n);                      // input
    for(i = 1; i <= n; i ++)    {
        scanf("%d", &a[i]);
    }

    count = 0;
    func(a, 2, n);
    printf("%d\n", count);
    return 0;
}

我编好了~不过在poj（2994）刷的时候超时了````您看看这程序哪里可以优化算法么？我是大一新生~望多指教~

#include<stdio.h>
#include<stdlib.h>
#include<memory>
#include<math.h>

int count;

int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;
}


void func(int a[], int x, int n)    {
    if(x == n + 1)
        return;
    qsort(a + x - 1, n - x + 2, sizeof(a[0]), cmp);
    count += a[x - 1] + a[x];
    a[x] += a[x - 1];
    func(a, x + 1, n);
    return;
}


int main()    {
    int i, n, a[10010];
    memset(a, 0, sizeof(a));              

    scanf("%d", &n);                      // input
    for(i = 1; i <= n; i ++)    {
        scanf("%d", &a[i]);
    }

    count = 0;
    func(a, 2, n);
    printf("%d\n", count);
    return 0;
}

int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;

这个返回的是什么哦 ，解释下啦

就是快排的cmp函数~你去搜下qsort用法就知道了~