IOI1994 北京2008的挂钟 迭代加深
2024-10-18 23:33:36
总的来讲,这是一道很⑨的题,因为:
(1)题目中有⑨个挂钟
(2)有⑨种操作方案
(3)这题因为解空间太小所以可以直接⑨重循环!!
这题可以用迭代加深搜索高效求解,剪枝的策略也很显然:
>所求的操作序列一定是单调不递减的
>同一操作不可能在解中出现4次及以上(操作4次等于没有操作)
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; ]={}; ]={}; ]={}; void move(int _cmd) { ++cmdCnt[_cmd]; switch(_cmd) { : ++dir[]; ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; break; : ++dir[]; ++dir[]; ++dir[]; ++dir[]; break; } } void undo(int _cmd) { --cmdCnt[_cmd]; switch(_cmd) { : --dir[]; --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; break; : --dir[]; --dir[]; --dir[]; --dir[]; break; } } inline bool isDest() { ;i<=;i++) ) return false; return true; } bool search_aux(int _maxDepth,int _curDepth,int _lastCmd) { if(isDest()) return true; if(_curDepth > _maxDepth) return false; ;i++) { ) { move(i); ,i); undo(i); if(next) { ++ans[i]; return true; } } } return false; } void input() { ;i<=;i++) scanf("%d",dir+i); } void search() { ;;i++) ,)) return; } void printAns() { ;i<=;i++) while(ans[i]--) printf("%d ",i); } int main() { input(); search(); printAns(); ; }
Cirno is willing to try this problem (*^__^*)
最新文章
- 转:在java中使用dom4j解析xml
- hadoop运维经验
- Mac OS X 安装ruby环境
- 迭代加深搜索 POJ 1129 Channel Allocation
- Jedis 操作
- sql 列设置默认值,语法查询知识点积累
- ORA-12012: error on auto execute of job &;quot;ORACLE_OCM
- [译]MVC应用程序生命周期
- Twitter数据抓取的方法(二)
- 用boost::bind构造boost::coroutine
- haproxy快速安装
- Linux磁盘和文件系统管理
- 项目实战2—实现基于LVS负载均衡集群的电商网站架构
- Django 系列博客(四)
- eventproxy 介绍这款好用的工具,前端事件式编程的思维
- 搜狗浏览器总是打开123.sogou.com-记搜狗浏览器遭遇劫持一例
- (网页)logback的使用和logback.xml详解(转)
- python 多进程练习 调用 os.system命令
- 利用FFMPEG命令进行文件分割
- Ubuntu安装ffmpeg