[人过留声哈]据说最难dp,看看谁能做出来!绝非作业,只是想看看谁能做出来(第一个做出来并没有人提出推翻数据的,有五十分可得) - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → [人过留声哈]据说最难dp,看看谁能做出来!绝非作业,只是想看看谁能做出来(第一个做出来并没有人提出推翻数据的,有五十分可得)

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 1669 人关注过本帖

标题：[人过留声哈]据说最难dp,看看谁能做出来!绝非作业,只是想看看谁能做出来(第 ...

取消只看楼主加入收藏

a351357741

等　级：论坛游民
帖　子：117
专家分：70
注　册：2010-9-15
结帖率：87.5%

楼主

已结贴√ 问题点数：50 回复次数：7

[人过留声哈]据说最难dp,看看谁能做出来!绝非作业,只是想看看谁能做出来(第一个做出来并没有人提出推翻数据的,有五十分可得)

对于给定的一张N*M(1 <= N,M <= 12)棋盘，求经过所有格子的哈密顿回路的个数。如下图所示，红色部分为不能经过的格子，绿色线条即为一个合法的方案。

图片附件: 游客没有浏览图片的权限，请登录或注册

注:算法时间限制(1s),若无人可解,本人讲发布题解网址(非广告)

[ 本帖最后由 a351357741 于 2010-9-28 22:05 编辑 ]

搜索更多相关主题的帖子: 作业　数据　推翻　

2010-09-28 21:58

a351357741

等　级：论坛游民
帖　子：117
专家分：70
注　册：2010-9-15

第 2 楼

得分:0

回复 2楼 jack10141

支持!

2010-09-28 22:12

a351357741

等　级：论坛游民
帖　子：117
专家分：70
注　册：2010-9-15

第 3 楼

得分:0

Sample Input
4 4
**..
....
....
....
Sample Output
2

2010-09-29 07:36

a351357741

等　级：论坛游民
帖　子：117
专家分：70
注　册：2010-9-15

第 4 楼

得分:0

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1814
可以从这个网站提交一下
原题目Ural 1519 Formula 1
百度一下可以找到的(包括题解但是不是我要发的)

2010-09-29 07:37

a351357741

等　级：论坛游民
帖　子：117
专家分：70
注　册：2010-9-15

第 5 楼

得分:0

给个提示:转载自 http://blog. 基于连通性的状态压缩动态规划
这道题显然可以暴搜，但是对于12*12的格子来说，也显然会相当严重的超时。就算是使用最牛叉的跳舞链也肯定无法在1s以内出解。所以我们必须要考虑一个特殊的方法来完成，而不能采用暴搜。

由于这道题的具有两个特殊性：一是数据范围不大，长宽均不超过12；二是棋盘模型。这不得不让我们联想到状态压缩动态规划。

上面是正解的网址!

2010-09-29 07:40