div color nod code sin stream 水题 翻译
有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。
现用汉语翻译为:
有 N 个区间,每个区间 x,y 表示提供的 x~y 共 y-x+1 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。
输入格式:
第一行,N,如题
接下来 N 行,每行一个数 x,y,如题
输出格式:
一个数,最多的区间数
输出样例 #1:
- 3
- 1 3
- 7 8
- 3 4
- 5
1<=n<=150000
0<=x<=y<=3000000
我太菜了...... 难受
第一遍写了个 zz 的贪心,刚写完就发现错误了
第二遍二维动归,迷之错误,现在我仍然不知道为什么二维是错的
第三遍改邪归正,老老实实地瞎写......
记录几句毒鸡汤:
1. 别学了,退役吧
2. 高考都这么菜,退役吧
3. 下学期就省赛了,你连这水题都不会做,退役吧
4. 待更新......
- 1#include 2#include 3#include 4#include 5 using namespace std;
- 6 int n,
- ans;
- 7 struct data {
- 8 int x,
- y,
- len;
- 9
- }
- node[2000010];
- 10 int f[4000010];
- 11 bool cmp(const data & aa, const data & bb) {
- 12
- return aa.y < bb.y;
- 13
- }
- 14 int main() {
- 15 scanf("%d", &n);
- 16
- for (int i = 1; i <= n; i++) {
- 17 scanf("%d%d", &node[i].x, &node[i].y);
- 18 node[i].len = node[i].y - node[i].x + 1;
- 19
- }
- 20 sort(node + 1, node + n + 1, cmp);
- 21
- for (int i = 1; i <= n; i++) {
- 22
- for (int j = node[i].y - 1; j >= 0; j--) {
- 23
- if (f[j]) break;
- 24 f[j] = ans;
- 25
- }
- 26 f[node[i].y] = max(f[node[i].x - 1] + node[i].len, ans);
- 27 ans = max(f[node[i].y], ans);
- 28
- }
- 29 printf("%d", ans);
- 30
- return 0;
- 31
- }
动态规划 洛谷 P1868 饥饿的奶牛
来源: http://www.bubuko.com/infodetail-2102482.html