原題

題目描述

有一條奶牛沖出了圍欄，來(lái)到了一處圣地（對(duì)于奶牛來(lái)說(shuō)），上面用牛語(yǔ)寫(xiě)著一段文字。

現(xiàn)用漢語(yǔ)翻譯為：

有?N?個(gè)區(qū)間，每個(gè)區(qū)間x,y?表示提供的x～y?共y?x+1?堆優(yōu)質(zhì)牧草。你可以選擇任意區(qū)間但不能有重復(fù)的部分。

對(duì)于奶牛來(lái)說(shuō)，自然是吃的越多越好，然而奶牛智商有限，現(xiàn)在請(qǐng)你幫助他。

輸入格式

第一行一個(gè)整數(shù)?N。

接下來(lái)?N?行，每行兩個(gè)數(shù)x,y，描述一個(gè)區(qū)間。

輸出格式

輸出最多能吃到的牧草堆數(shù)。

輸入輸出樣例

輸入 #1

3
1 3
7 8
3 4

輸出 #1

5

說(shuō)明/提示

解題思路

動(dòng)態(tài)加二分。

構(gòu)造一個(gè)結(jié)構(gòu)體存儲(chǔ)元素，然后按照r從小到大排序。

dp[i]=max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]+cow[i].val)

lower_bound(二分查找) 最后一個(gè)沒(méi)有和cow[i].l相交的元素，尋找到后取最大的那個(gè)區(qū)間。

AC代碼

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1.5e5+5; 
struct Cow{int l,r;int val;bool operator <(const Cow b){return r<b.r;}
}cow[N];
int n,dp[N];
int lower_bound(int l,int r,int k){int ans=0;while(l<r){int mid=(l+r)>>1;if(cow[mid].r<k)  {ans=mid;l=mid+1;}else r=mid;}return ans;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&cow[i].l,&cow[i].r);cow[i].val=cow[i].r-cow[i].l+1; }sort(cow+1,cow+n+1);for(int i=1;i<=n;i++){dp[i]=max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]+cow[i].val);}printf("%d",dp[n]);return 0;
}