P3957 [NOIP2017 普及组] 跳房子
思路：首先发现单调性，灵活性增加 \(x+1\) 的答案肯定不会比增加 \(x\) 的答案更劣。
那么可以二分求 \(g\)，则机器人每次可以移动 \([\max(d-mid,1),d+mid]\) 这个区间内的距离，为了方便，设为 \(\)。
考虑动态规划求得能走到的最大分数，令 \(dp_i\) 表示走到第 \(i\) 个格子的最大分数，则状态转移方程为：
\ dp_j\]
可以使用单调队列维护：
[*]若当前队尾为 \(j\)，且 \(x_j < x_i - r\)，则这个 \(j\) 无法对 \(dp_i\) 造成贡献，直接不断弹出即可。
[*]若当前队头为 \(j\)，且 \(x_{j+1} \le x_i - l\)，则这个 \(j+1\) 可以对 \(dp_i\) 造成贡献，不断插入即可。
[*]因为要维护最大值，可以使用单调队列。
时间复杂度为 \(O(N \log W)\)。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=5e5+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c 东西不错很实用谢谢分享 用心讨论，共获提升！ 热心回复！ 前排留名，哈哈哈 感谢，下载保存了 用心讨论，共获提升！ 这个好，看起来很实用 分享、互助 让互联网精神温暖你我 这个好，看起来很实用 前排留名，哈哈哈 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 收藏一下 不知道什么时候能用到 鼓励转贴优秀软件安全工具和文档！ 热心回复！ 谢谢楼主提供！ yyds。多谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ yyds。多谢分享 谢谢分享，试用一下
页:
[1]
2