題目描述

有一條奶牛沖出了圍欄，來到了一處圣地（對于奶牛來說），上面用牛語寫著一段文字。

現用漢語翻譯為：

有N個區間，每個區間x，y表示提供的x~y共y-x+1堆優質牧草。你可以選擇任意區間但不能有重復的部分。

對于奶牛來說，自然是吃的越多越好，然而奶牛智商有限，現在請你幫助他。

輸入輸出格式

輸入格式：

?

第一行，N，如題

接下來N行，每行一個數x，y，如題

?

輸出格式：

?

一個數，最多的區間數

?

輸入輸出樣例

輸入樣例#1：
3 1 3 7 8 3 4 輸出樣例#1：
5

說明

1<=n<=150000

0<=x<=y<=3000000

分析：線段覆蓋的題一般來說都可以用dp做，而且方式就那么幾個.一種是長度特別大，線段非常少的,而且線段數量有限制，例如：傳送門，這個時候只能用線段作為狀態.這道題線段和長度都非常大，只能有一維，如果設線段的話，我不知道是否和前一個線段重疊，不好處理，那么只能設坐標為狀態。那么設f[i]表示1~i中能覆蓋到的最多的點的個數，先把線段按照右端點排序，如果當前枚舉到的這個點正好位于線段內，那么這個線段不能覆蓋，那么f[i] = max{f[j]}(j < i),否則f[i] = max{f[當前線段的左端點l - 1] + r - l + 1}.當然，你也可以選擇不覆蓋,那么答案就是我們之前處理好的最大值.這道題和noip2010引水入城有異曲同工之妙.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath>using namespace std;int n,f[3000010],maxx;struct node {int x,y; }a[150010];bool cmp(node a,node b) {return a.y < b.y; }int main() {scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a + 1, a + 1 + n,cmp);for (int i = 1; i <= n; i++){for (int j = a[i].y - 1; j >= 0; j--){if (!f[j])f[j] = maxx;elsebreak;}f[a[i].y] = max(maxx,f[a[i].x - 1] + a[i].y - a[i].x + 1);maxx = max(maxx,f[a[i].y]);}printf("%d\n",f[a[n].y]);return 0; }

?

轉載于:https://www.cnblogs.com/zbtrs/p/7485495.html

總結

以上是生活随笔為你收集整理的洛谷P1868 饥饿的奶牛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。