求解一些关于单调性优化dp的问题

1 一个数轴上有一些点，从1号点开始跳，每个点都可以跳到任何一个比他坐标更大的点，但是对于每个点都要付出一个固定的代价vi和跳跃的距离乘上ki，求跳到比坐标比l更大的点的代价的最小值求此题详解
2 如果我通过暴力什么的发现决策单调，但是连表达式都分析不明白，有没有什么比较好的解题策略
3 单调性，单调队列，凸包，他们之间到底有什么不得不说的关系

2楼……话说我最近这么水会不会被水贴红色警报

用单调性优化动态规划
凸完全单调性的加强与应用
算法合集之《从一类单调性问题看算法的优化》
动态规划加速原理之四边形不等式
动态规划的斜率优化
1D1D动态规划优化初步
暂时能想到的

其实蒟蒻会说回答您是为了复习单调性dp么? rp:=rp<<rp;
要是ki满足单调性就是裸斜率DP不用说了
否则我们鼓捣鼓捣裸DP方程可得
f[i]=min{ f[j]+v[j]-jk[j] + ik[j] },f[i]=min{ X[j] + iY[j] }
可以看作是一个斜率 -(1/i) 的直线去切凸壳
然后这个斜率是单调的仍然是可以单调队列就不用动态凸壳或者cdq分治
您艹完那几篇论文就懂蒟蒻的叙述了,欢迎神牛打脸"蒟蒻叙述挫完"

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

12回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六