[求助]石子归并问题 - C语言论坛

编程论坛 → 开发语言 → 『 C语言论坛』 → [求助]石子归并问题

标题：[求助]石子归并问题

只看楼主

Eastsun

等　级：贵宾
威　望：32
帖　子：802
专家分：0
注　册：2006-12-14

第 21 楼

得分:0

回溯+剪枝足矣
ps:为什么我这里打不开acm.tongji.edu.cn?

My Blog→Click Me

2007-08-03 18:08

cwande

等　级：新手上路
威　望：3
帖　子：333
专家分：0
注　册：2006-8-18

第 22 楼

得分:0

以下是引用leeco在2007-8-3 16:14:00的发言：
超内存了

用bool就不会超了

汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．

2007-08-03 18:27

leeco

等　级：贵宾
威　望：10
帖　子：1026
专家分：177
注　册：2007-5-10

第 23 楼

得分:0

回复：（卧龙孔明）以下是引用leeco在2007-8-3 16:14:...

优化了还是超的

2007-08-03 20:01

leeco

等　级：贵宾
威　望：10
帖　子：1026
专家分：177
注　册：2007-5-10

第 24 楼

得分:0

回复：（Eastsun）回溯+剪枝足矣ps:为什么我这里打不开...

一年前我就打不开了。

2007-08-03 20:03

卧龙孔明

等　级：贵宾
威　望：59
帖　子：3872
专家分：684
注　册：2006-10-13

第 25 楼

得分:0

以下是引用leeco在2007-8-3 20:01:00的发言：
优化了还是超的

反正DP极速，可以将正在运算和即将运算的放在内存，空闲的存于文件

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.

2007-08-04 08:00

crackerwang

等　级：新手上路
威　望：8
帖　子：833
专家分：0
注　册：2007-2-14

第 26 楼

得分:0

最容易想到的应该是O(n^3)的动归和回溯.
dp[i][j]表示把第i堆到第j堆合并的最小差值
所以dp[i][j]=min{abs(dp[i][k]-dp[k][j])}; i<=k<=j;
答案应该是dp[1][n];
不知道到O(NW)的怎么做不知道到O(NW)的怎么做

[此贴子已经被作者于2007-8-4 14:33:50编辑过]

2007-08-04 14:30

crackerwang

等　级：新手上路
威　望：8
帖　子：833
专家分：0
注　册：2007-2-14

第 27 楼

得分:0

以下是引用Eastsun在2007-8-3 18:08:00的发言：
回溯+剪枝足矣
ps:为什么我这里打不开acm.tongji.edu.cn?

我也进不去.

2007-08-04 14:35

cwande

等　级：新手上路
威　望：3
帖　子：333
专家分：0
注　册：2006-8-18

第 28 楼

得分:0

以下是引用crackerwang在2007-8-4 14:30:00的发言：
最容易想到的应该是O(n^3)的动归和回溯.
dp[i][j]表示把第i堆到第j堆合并的最小差值
所以dp[i][j]=min{abs(dp[i][k]-dp[k][j])}; i<=k<=j;
答案应该是dp[1][n];
不知道到O(NW)的怎么做不知道到O(NW)的怎么做

你没看题目吧-_-

汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．

2007-08-04 18:31

crackerwang

等　级：新手上路
威　望：8
帖　子：833
专家分：0
注　册：2007-2-14

第 29 楼

得分:0

我理解成合并相邻的了.