首页 > 分享 > 洛谷 P3957 跳房子

洛谷 P3957 跳房子

花匠小妙招
2024-12-09 10:18

传送门：洛谷 P3957 跳房子
算法分析：由特殊到一般
(Section A)
首先考虑：若 (g=0) 时的动态规划
不难发现，当前这个格子 (x) 一定是从 (x-d) 跳来的
(Section B)
其次考虑：(g) 改变时的动态规划
不难发现，当前这个格子 (x) 一定是从 (x-(d+g)) 到 (x-(d-g)) 跳来的，那么只要枚举 (jin[0,i-1]) 即可求出最大值，最外层用循环判断 (g) 是否合适（时间复杂度：(O(n^2times maxS))，预估得分：(20) 分）
(Section C)
之后考虑：(g) 的枚举问题
不难发现，设 (A) 为满足条件的答案集合，对于 (forall g_1,g_2)，满足 (g_1in A) 且 (g_1<g_2) ，则 (g_2in A)，即元素必定单调递增，如果小的行，大的更行。对于这一性质，可以用二分法来寻找最小值
（时间复杂度：(O(n^2times log_{maxS}))，预估得分：(50) 分）
(Section D)
最后考虑：(dp) 的最值优化，即单调队列维护区间最大值。由于区间长度恒为 (2g) ，故可行。
（时间复杂度：(O(n log_{maxS}))，预估得分：(100) 分）

时间复杂度：(O(nlog{maxS}))

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxN=500000; const long long inf=-922337203685477580; struct Node { int pos,pt; }a[maxN+1]; struct queue { int pos; long long v; }q[maxN+1]; int n,d,k,ans=-1,maxT=0,q_tail=0,q_head=0; long long dp[maxN+1],tot=0; bool check(int); inline int read(); int main() { n=read(); d=read(); k=read(); for(int i=1;i<=n;i++) { a[i].pos=read(); a[i].pt=read(); maxT=max(a[i].pos,maxT); } int l=0,r=maxT,mid; while(l<=r) { mid=(l+r)/2; if(check(mid)) {ans=mid; r=mid-1;} else l=mid+1; } printf("%d",ans); return 0; } bool check(int g) { for(int i=0;i<=n;i++) dp[i]=inf; tot=0; dp[0]=0; memset(q,0,sizeof(q)); q_head=q_tail=0; q_head++; int l=max(1,d-g),r=d+g,j=0; for(int i=1;i<=n;i++) { while(a[i].pos-a[j].pos>=l && j<i) {while(q_head<=q_tail && q[q_tail].v<=dp[j]) q_tail--;q[++q_tail].pos=j;q[q_tail].v=dp[j++]; } while(q_head<=q_tail && a[i].pos-a[q[q_head].pos].pos>r) q_head++; if(q_head<=q_tail) dp[i]=max(dp[i],q[q_head].v)+a[i].pt; } for(int i=1;i<=n;i++) tot=max(dp[i],tot); return (tot>=k); } inline int read() { char ch=getchar(); int f=1,num=0; while((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();} while(ch>='0' && ch<='9') { num=num*10+ch-'0'; ch=getchar(); } return num*f; }