把一块长度为L的木棒切成N块，每段的大小必须为a1,a2,…,an，每一次切木棒的代价为当前木棒的长度，完成切割任务的最小代价？

[IwfWcf]

Input
首先输入T，有T个测试用例
每个测试用例输入两行
第一行整数L和N。接下来一行是N个数表示每一段的木棒长度。 

Output
求完成任务的最小代价

Sample Input
2
10 4
1 2 3 4 
306 8
120 37 42 42 32 2 7 24

Sample Output
19
785 

[Navi]

反过来想每次合并是两段长度之和。于是就变成了Huffman问题了。

2012/5/24 IwfWcf <iwf...@gmail.com>

--
Sincerely,

Junyuan Zhuang (Navi)

Email: nav...@gmail.com
Twitter: http://twitter.com/navimoe

[baizhiwei9]

我没看懂，代价不是恒定的吗？就是木棒的长度呀

[IwfWcf Zhang]

Navi的Solution是对的

解释一下样例一，10分割为4和6，代价为10，6分割为3和3，代价为6，3分割为1和2，代价为3。总代价为10+6+3，即Huffman树中非叶节点的权值和。

[Junkun Huang]

霍夫曼树解法的确是一种“美妙”的解决方案啊。我刚开始看到这问题倒没想到霍夫曼。倒是其他思路：

解法一：

1 降序排序集合A{a1,a2,…,an} 。

2 遍历集合A，计算每次切木棒代价cost_i。针对前后相同的元素，ai==aj，特殊计算：

先切出木棒2*a1，再从2*ai木棒对半切分。

3 以上切木棒过程，累加不同cost_i，得到cost_sun即求结果。

看似OK，跑了几个简单测试用例，包括上面的两个用例，均通过。不过想想觉得不太对劲。

可以猜想知道，对于复杂的测试案例结果就错误了。留给你稍微想想吧:-)

解法二：

（霍夫曼解法，在此不详细了……）

后来，实现了霍夫曼解法，对于比较复杂的案例，两种解法得到结果对比，终于可以明确解法一的不足地方了！

相关的实现可参见：

https://github.com/huangjunkun/algorithm/blob/master/huffman_use_case.cpp 

在 2012年5月24日星期四UTC+8下午12时20分18秒，IwfWcf写道：

[IwfWcf]

Orz……有必要写那么长吗……帖一下我的代码……

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

inline bool cmp(int a, int b)
{
return a > b;
}

int main()
{
int t;
scanf("%d", &t);
for (int cases = 0; cases < t; cases++) {
int l, n;
scanf("%d%d", &l, &n);
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
make_heap(a.begin(), a.end(), cmp);
int ans = 0;
for (int i = 1; i < n; i++) {
int n1 = a.front();
pop_heap(a.begin(), a.end(), cmp), a.pop_back();
int n2 = a.front();
pop_heap(a.begin(), a.end(), cmp), a.pop_back();
a.push_back(n1 + n2), ans += n1 + n2;
push_heap(a.begin(), a.end(), cmp);
}
printf("%d\n", ans);
}
return 0;
}

在 12-5-25，Junkun Huang<huang...@gmail.com> 写道：