| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1306 人关注过本帖
标题:zoj2749求思路
只看楼主 加入收藏
小鱼儿c
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:852
专家分:1317
注 册:2011-4-1
收藏
得分:17 
算法这么激情 哦。。
我帮顶

用心做一件事情就这么简单
2012-04-11 00:18
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 10楼 卧龙孔明
连通性状态压缩dp   求指导啊
2012-04-11 09:05
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:17 
惭愧地表示连通性动态压缩dp从来都没懂过
到这找熟人来的,请主动无视我,喵~

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2012-04-11 21:50
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:17 
哎,一直WA怎么破?

话说我求出答案每次都拐很多弯走一大堆0这个应该没问题吧?
2012-04-13 10:08
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 14楼 czz5242199
没问题的, 只要可行解就可以, 我刚开始看错了, 一直在求最优解,呵呵
4天过去了,还是不会啊
2012-04-13 14:28
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
最近工作很忙,连写代码的时间也没有。呵呵,希望明天我能有时间实际试试。

这题确实类似于哈密尔顿路,但并不是,因为灰色格的存在。
还有比较质疑孔明估计的复杂度。O(n*m*2^n)由于n、m <= 10,所以这个估计的规模只有10万级,怎么做也不过几个毫秒的事。如果真有这样的算法我真想看看。
DFS的复杂度应该是O(C^nm)。这里的C介于1至4之间,我无法分析出准确的C值。

目前我只能从剪枝入手。简单分析一下可以得到这样的剪枝条件:

连线在任何一行上只能经过一种颜色的格子。也就是说如果连线已经在这行上经过了黑(白)格子就不能再进入这一行上的白(黑)格子。
在起点和终点所在的行只能经过这两点颜色的格子。

希望明天能试一下。其他朋友可以参考我的剪枝条件。如果试了请告诉我效果如何(我不一定有时间能自己写代码玩了)呵呵

重剑无锋,大巧不工
2012-04-14 00:30
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 16楼 beyondyf
我第一次写就用你说的剪枝了, 可是TL了,  可能我代码写的撮了点也有关系
2012-04-14 19:28
快速回复:zoj2749求思路
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025613 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved