USACO 5.4 tour的dp解法
2024-09-03 12:21:59
题意:有n个点排成序列,两个人甲乙从1出发,到达n,中间的点不允许到达两次,只能从左向右走,问最多两人访问多少点。
(膜大佬)
解:
dp
f(i, j) 表示甲到了i点,乙到了j点,两人最多访问了多少点。
关键性质:f(i, j) = f(j, i) ***
分析这个问题
(1) f(i, j) = 0 (i == j)
从而i始终不等于j
深入分析这个问题:
甲与乙的路径必然是相互交叉的!!!
我在dp转移的时候,我保证
f(i, j) = max{ f(k, j) + 1 } (i到k有边),max{k, j} <= i
这样,转移一定是合法的。
而且,必然能**覆盖到**最优解!!,因为最优解必然是一个相互交叉的情况。
不能保证每个 f(i, j) 是最优解,但是可以保证 max{ f(i, n) + 1} (i到n有边)必然是最优解。
最新文章
- Jquery更改table中的内容(一)
- windows 共享文件夹 给 mac
- OpenMP对于嵌套循环应该添加多少个parallel for 分类: OpenMP C/C++ Linux 2015-04-27 14:48 53人阅读 评论(0) 收藏
- Kibana安装及部署
- debug和release转载
- n阶乘 尾数0的个数
- Java 前端加密传输后端解密以及验证码功能
- UVA 10305 Ordering Tasks
- Ubuntu 12.04 中文输入法
- [BZOJ2820][Luogu2257]YY的GCD
- web前端HTML基础
- java判断A字符串是否包含B字符串
- Cocos2D iOS之旅:如何写一个敲地鼠游戏(二):Cocos2D中的高清支持
- 访问者模式 Visitor 行为型 设计模式(二十七)
- SQL 性能优化 总结
- 【2018.04.19 ROS机器人操作系统】机器人控制:运动规划、路径规划及轨迹规划简介之一
- 【2】IOS APP打包发布
- ubuntu 安装(install) pwntcha[一个做";验证码识别";的开源程序]
- STL list用法总结
- 【WebGL】2.基础概念
热门文章
- Java8 本地DateTime API
- 构建可读性更高的 ASP.NET Core 路由
- linux shell操作
- [Testing] Config jest to test Javascript Application -- Part 2
- 使用UltraISO刻录自己的音乐CD步骤
- apache多网站配置
- linux的主分区与逻辑分区的关系
- snip_进制转换代码段
- PHP琐碎学习
- 2016/05/25 PHP mysql_insert_id() 函数 返回上一步 INSERT 操作产生的 ID