题解 P3957 【跳房子】

深感此题超纲。。。 首先注意到，如果花费g枚金币可以得到k分，那么花费g+1枚也一定可以。也就是说，可以二分g。 那么，如何判断花费g枚金币是否可行呢？ 考虑dp，dp[i]表示跳到格子i时获得的最大分数。 显然可以这样更新： ```cpp dp[0]=0LL; for(int i=1;i<=n;i++){ dp[i]=-INF; for(int j=0;j<i;j++) if(pos[i]-pos[j]>=mind&&pos[i]-pos[j]<=maxd) dp[i]=max(dp[i],dp[j]+s[i]); } ``` 这是O(n^2)的，总体复杂度O(n^2\*log(ans))，能过50%的数据。 ```cpp int l=0,r=0; for(int i=1;i<=n;i++){ dp[i]=-INF; while(pos[i]-pos[r]>=mind)r++; while(pos[i]-pos[l]>maxd)l++; for(int j=l;j<r;j++) dp[i]=max(dp[i],dp[j]); dp[i]+=s[i]; } ``` 我们发现，dp[i]是由dp[l...r)的最大值转移而来，其中区间[l...r)随着i的增加只会向右滚动。另外dp[i]可以写成max(dp[k])(l<=k<r)+s[i]的形式。这……不是deque优化的充分条件么？ 使用一个单调队列维护一下[l...r)内的dp值即可。 单调队列优化的dp时间复杂度为O(n)线性，总复杂度为O(n log(ans))。 为了防止被ccf老爷机卡掉，还是贴手写deque（其实就几行）吧……【djq在场上没有手写担心被卡常】 ```cpp #define rep(i,n) for(int i=0;i<(n);i++) #define rep1(i,n) for(int i=1;i<=(n);i++) #define MP make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1e9+7; int n,pos[500005],num[500005]; ll dp[500005]; int frt,rr; pair<ll,int> cur[500005]; inline void ins(pair<ll,int> ele){ while(frt<rr&&cur[rr-1]<ele)rr--; cur[rr++]=ele; } inline void era(pair<ll,int> ele){ if(frt<rr&&cur[frt]==ele)frt++; } inline ll maxi(){ return frt>=rr?(-1LL<<60):cur[frt].first; } bool check(int mind,int maxd,int lim){ int l=0,r=0; frt=rr=0; dp[0]=0LL; rep1(k,n){ while(pos[k]-pos[r]>=mind){ ins(MP(dp[r],r));r++; } while(pos[k]-pos[l]>maxd){ era(MP(dp[l],l));l++; } dp[k]=maxi()+num[k]; if(dp[k]>=lim)return true; } return false; } int main(){ // freopen("jump.in","r",stdin); // freopen("jump.out","w",stdout); int d,lim; scanf("%d%d%d",&n,&d,&lim); rep1(k,n)scanf("%d%d",&pos[k],&num[k]); int l=0,r=INF; while(l<r){ int mid=(l+r)>>1; if(check(max(d-mid,1),d+mid,lim))r=mid; else l=mid+1; } printf("%d\n",r==INF?-1:r); return 0; } ```