BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP)-白红宇

BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP)

阅读量：5115 次

发布时间：2019-06-13

本文共 1665 字，大约阅读时间需要 5 分钟。

Time Limit: 10 Sec Memory Limit: 256 MB

Submit: 1747 Solved: 876

[ ][ ][ ]

Description

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

Input

第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi

Output

一个整数，表示最少有几个人说谎

Sample Input

2 0

0 2

2 2

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
     
      #include
      
       #include
       
        #include
        #include
         
          #define Pair pair
          
           #define LL long long const int MAXN = 100001;using namespace std;#include
           
            #include
            
             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
             
              v[MAXN];int f[MAXN];cc_hash_table
              
               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;}