跳房子

去年pjT4

为什么今天才做这个水题呢?

昨天突然被告知今年不能打普及了。。。。虽然很不甘心,但还是把机会留给其他初中同学们把。。。

QAQ

滑动窗口板子题啊。。二分答案g后就是一段区间dp最大,,,就是个滑动窗口板子啊QAQ
中间有一句有点坑,,check中当队列为空了,不能直接return,因为还可能从滑动窗口后面的一个点(可以被跳到)往后。

因此是把dp赋值inf而不是。。。return false…(开始因此wa了3点

(好像也没啥其他可以说的了((当时的我只会dfs+二分答案甚至不会dp((然后re*8 滚粗

今年tg 努力吧!

/*Heroes Never Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
typedef long long ll;
#define MAXN 500006
#define inf 0x3f3f3f3f3f3f3f3f
ll s[MAXN] , w[MAXN] , dp[MAXN] , q[MAXN] , head , tail;
ll n , d , k ;
bool check( ll g );
int main(){
    cin >> n >> d >> k;
    for( ll i = 1 ; i <= n ; ++i )
        scanf( "%lld%lld" , &s[i] , &w[i] );
    ll l = 0 , r = s[ n - 1 ];
    while( l <= r ) {
        ll m = l + r >> 1;
        if( check(m) )
            r = m - 1;
        else l = m + 1;
    }
    cout << (l == s[n-1] + 1 ? -1 : l);
}
bool check( ll g ){
    memset(dp,0,sizeof dp),memset(q,0,sizeof q);
    ll l = max( d - g , 1LL ) , r = d + g;
    head = -1 , tail = 0;
    q[ ++ head ] = 0,dp[0] = 0;
    ll p = 1 , j = 0 ;while( s[p] < l ) ++ p;
    for( ll i = p; i <= n ; ++ i ){
        while( s [i] - s[ j + 1 ] >= l ) {
            ++ j;
            while (dp[j] >= dp[ q[tail] ] && head <= tail) --tail;
            q[ ++tail ] = j;
        }
        while( s[ i ] - s[ q[head] ] > r && head <= tail ) ++ head;
        if( head > tail ) dp[i] = -inf; //return false;///////
        else dp[ i ] = dp[ q[ head ] ] + w[i];
        if( dp[ i ] >= k ) return true;
    }
    return false;
}