BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP)
2018-06-17 20:29:27来源:未知 阅读 ()
Submit: 1747 Solved: 876
[Submit][Status][Discuss]
Description
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<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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 哈尔滨网络热身赛 2019-11-25
- 两个数的差 2019-10-16
- 带毒的水 2019-08-16
- CCPC2019江西省赛-Problem G.Traffic 2019-08-16
- [Algorithm] 1. A+B Problem 2018-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash