BZOJ2298: [HAOI2011]problem a(帶權區間覆蓋DP)

Description

Input

第一行一個整數n，接下來n行每行兩個整數，第i+1行的兩個整數分別代表ai、bi

Output

一個整數，表示最少有幾個人說謊

Sample Input

Sample Output

HINT

100%的數據滿足： 1≤n≤100000   0≤ai、bi≤n

Source

感覺這是個語文題。

我們翻譯一下每個人說的話

就變成了：我的排名為$a_i + 1$，和我分數相同的有$N - b_i-a_i$個

因此我們可以把$a+1,N-bi$抽象為一段區間，註意不同的區間可能相同，但這並不矛盾

然後就變成了帶權區間覆蓋問題

一種做法是套路排序+二分

另一種是處理出所有區間和所有區間的出現次數(用map記錄)

用$f[i]$表示到名詞為$i$時，有多少人說了真話

轉移的時候枚舉所有以$i$為結尾的區間就可以

註意區間$[l,r]$的出現次數最多為$r-l+1$次

第二種方法可以用hash做到$O(N)$（不過死活卡不過去之好用cc_hash_table）

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#define Pair pair<int, int>
#define LL long long 
const int MAXN = 100001;
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N; 
vector<int>v[MAXN];
int f[MAXN];
cc_hash_table<LL, int>mp;
LL MP(LL a, LL b) {
    return a + b * 100000;
}
int main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #else
    #endif
    N = read();
    for(int i = 1; i <= N; i++) {
        int a = read(), b = read();
        a++; b = N - b;
        if(a > b) continue;
        if(++mp[MP(a, b)] == 1) v[b].push_back(a);
    }
    for(int i = 1; i <= N; i++) {
        f[i] = f[i - 1];
        for(int j = 0; j < v[i].size(); j++) 
            f[i] = max(f[i], f[v[i][j] - 1] + min(mp[MP(v[i][j], i)], i - v[i][j] + 1));
    }
    printf("%d", N - f[N]);
    return 0;
}