BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP)
BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP)
attack
发布于 2019-01-30 16:03:43
发布于 2019-01-30 16:03:43
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
3 2 0 0 2 2 2
Sample Output
1
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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-06-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录