题解 P3957 【跳房子】

· · 题解

NOIP2017普及组T3

作为一个初一蒟蒻，这道题是真的恶心

我一开始的想法是直接dp，定义dp[i][j]为但只考虑前i个格子，并且用j元改造时的最优解 那么就可以列出转移方程

dp[i][j] = max(d[k][j]+a[i])(dis[i]-dis[k] \in [lg, rg])

先不说方程正确与否，这个解法的复杂度为O(n^3)，显然基本没分

所以，我们来仔细观察一下这道题，然后我们就会发现，但如果用i个金币改造依然无法获得k分的话，那么j(j<i)显然也不能

也就是说，这道题是具有单调性的

于是我们就可以想到这道题可以二分答案


int main(){
    scanf("%lld%lld%lld", &n, &d, &q);
    for(long long int i = 1; i <= n; i++) scanf("%lld%lld", &bs[i].d, &bs[i].p), r = max(r, bs[i].d);
    r = 1005;
    while(l < r){
        mid = (l + r) / 2;
        if(dp_check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

但是，要如何检查用i个金币是否能够获得k分呢

不(hen)难想到，可以使用dp，定义dp[i]为到第i个格子时的最大值，容易列出转移方程

dp[i] = max(dp[k]+a[i])

然后再加上一些小优化，就OK啦

很多人说要单调队列，但是我dp加优化也过了就是了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define maxn 500010
using namespace std;
struct block{
    long long d, p;
} bs[maxn];
long long n, d, q, f[maxn], l, r, mid; 注意开long long
bool dp_check(long long g){
    memset(f, -127, sizeof(f)); f[0] = 0;
    long long int lg = d - g, rg = d + g;
    if(lg <= 0) lg = 1;
    for(long long int i = 1; i <= n; i++){
        for(long long int j = i-1; j >= 0; j--){
            if(bs[i].d-bs[j].d >= lg && bs[i].d-bs[j].d <= rg) f[i] = max(f[i], f[j] + bs[i].p);
            else if(bs[i].d-bs[j].d > rg) break; 优化1
        }
        if(f[i] >= q) return true; 优化2
    }
    return false;
}
int main(){
    scanf("%lld%lld%lld", &n, &d, &q);
    for(long long int i = 1; i <= n; i++) scanf("%lld%lld", &bs[i].d, &bs[i].p), r = max(r, bs[i].d);
    r = 1005;
    while(l < r){
        mid = (l + r) / 2;
        if(dp_check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}