ToB企服应用市场:ToB评测及商务社交产业平台

标题: P3957 [NOIP2017 遍及组] 跳房子 [打印本页]

作者: 羊蹓狼 时间: 2024-7-31 20:59
标题: P3957 [NOIP2017 遍及组] 跳房子
思路：

起首发现单调性，灵活性增加 \(x+1\) 的答案肯定不会比增加 \(x\) 的答案更劣。
那么可以二分求 \(g\)，则机器人每次可以移动 \([\max(d-mid,1),d+mid]\) 这个区间内的距离，为了方便，设为 \([l,r]\)。
考虑动态规划求得能走到的最大分数，令 \(dp_i\) 表示走到第 \(i\) 个格子的最大分数，则状态转移方程为：

\[dp_i = s_i + \max\limits_{j=0}^{i-1} [x_i - r \le x_j] [x_j \le x_i - l] 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)\)。
完整代码：

[code]#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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)