关键词:
题目描述
有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。
现用汉语翻译为:
有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。
输入输出格式
输入格式:
第一行,N,如题
接下来N行,每行一个数x,y,如题
输出格式:
一个数,最多的区间数
输入输出样例
3 1 3 7 8 3 4
5
说明
1<=n<=150000
0<=x<=y<=3000000
/* a[i][0]表示i位置是否为某一区间的起点 a[i][1]表示以i为起点的区间的价值 f[i]表示到i位置的最大价值是多少 因为不允许区间重叠,所以一旦选了某个区间,其他的价值只能来自这个区间之外 考虑从前往后进行状态转移 那么f[i+a[i][1]]=max{f[i]+a[i][1]} 其中i必须保证是区间i的起点 */ #include<iostream> #include<cstdio> using namespace std; int n,a[3000010][2],r,f[3000010]; int main(){ scanf("%d",&n); int x,y; for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); a[x][0]=1;a[x][1]=y-x+1; r=max(r,y); }r++; for(int i=1;i<=r;i++){ f[i]=max(f[i],f[i-1]); if(a[i][0]){ f[i+a[i][1]]=max(f[i+a[i][1]],f[i]+a[i][1]); } } printf("%d",f[r]); }
p1868饥饿的奶牛
P1868饥饿的奶牛题目描述有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。现用汉语翻译为:有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的... 查看详情
题解p1868饥饿的奶牛(代码片段)
题目链接:P1868饥饿的奶牛题面有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。现用汉语翻译为:有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有... 查看详情
p1868饥饿的奶牛[dp](代码片段)
P1868饥饿的奶牛一句话题意:给(n)个区间,区间可以任意选但不能有重复部分,求能选到的最大的点数。做法:显然要弄一个(dp[i])表示([0,i])能吃到多少草。先把所有的区间双关键字从小到大排序。然后遍历所有的点,找到相对... 查看详情
[luogup1868]饥饿的奶牛(dp)
传送门 先把所有区间按照左端点排序f[i]表示区间0~i的最优解 #include<cstdio>#include<iostream>#include<algorithm>#definemax(x,y)((x)>(y)?(x):(y))intn,v;intf[3000001];structnode{ intx,y;}p[150001]; 查看详情
清北前紧急补课6饥饿的奶牛(代码片段)
题目描述有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。现用汉语翻译为:有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。对于奶牛... 查看详情
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
[wc2002][洛谷p1578]奶牛浴场
洛谷题解里那个人可真是话多呢。 题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛... 查看详情
洛谷p1154奶牛分厩
P1154奶牛分厩农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教... 查看详情
洛谷——p1154奶牛分厩
P1154奶牛分厩题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因... 查看详情
洛谷p1154奶牛分厩
题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会... 查看详情
洛谷p1535游荡的奶牛(代码片段)
P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情
洛谷1578:[wc2002]奶牛浴场——题解(代码片段)
https://www.luogu.org/problemnew/show/P1578#sub由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个... 查看详情
洛谷p1472奶牛家谱cowpedigrees
P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高 提交 讨论 题解 最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情
bzoj1669:[usaco2006oct]hungrycows饥饿的奶牛dp+树状数组+hash
最长上升子序列。虽然数据可以直接n方但是另写了个nlogn的转移:f[i]=max(f[j]+1)(a[j]<a[i])O(n^2)#include<iostream>#include<cstdio>usingnamespacestd;constintN=5005;intn,a[N],f[N],ans;intread()intr=0,f=1;charp=getcha 查看详情