题解 P3957 【跳房子】

忽然感觉楼下大佬们的题解好复杂的样子（还有90分过不了的），然后我就发一个分分钟能过的朴素算法好了（~~而且超朴素的样子什么优化都去见鬼好了~~）： ```cpp #include<bits/stdc++.h> typedef long long ll; #define M 500005 using namespace std; ll n,d,k,l,r=1005; //这里你可以改成1e5+5试一下，照样AC！ ll ans=-1; ll far[M],val[M],f[M]; ll read() { char c=getchar(); ll x=0,f=1; while(!isdigit(c) && c!='-') c=getchar(); if(c=='-') { f=-1; c=getchar(); } while(isdigit(c)) { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } return x*f; } bool check(ll g) //这里就体现了朴素啊。。什么单调优化双端队列之类的都去见鬼好了 { memset(f,128,sizeof(f));f[0]=0; for(int i=0;i<n;++i) //就是个二维，没见的爆了啊？嗯哈？ //因为循环里还有剪枝的啊你这么担心爆爆爆的干啥？ //朴素点不好去整些优化啥的还爆了？（对自己说的） for(int j=i+1;j<=n;++j) { if(far[j]-far[i]>d+g) break; if(far[j]-far[i]<max(d-g , (ll)1)) continue; f[j]=max(f[j] , f[i]+val[j]); if(f[j]>=k) return true; } return false; } int main() //主程序还是挺简洁的，差不多就一个读入和二分查找 { n=read(); d=read(); k=read(); for(int i=1;i<=n;++i) { far[i]=read(); val[i]=read(); } ll mid; while(l<=r) { mid=(l+r)>>1; check(mid)? ans=mid,r=mid-1 : l=mid+1; } printf("%lld\n",ans); return 0; } ``` 然后我算了一下，如果说是二分1e5的话，常数大概就是log(1e5)=17 了，这难道还不省啊？~~再加上数据也不会坑到说让你整个二重循环走一遍~~，所以。。。。所以。。。。就这样了啊！O( < 17*1e10 ) 的算法还是过了~~~~~~~~~~