洛谷P1868 饥饿的奶牛。P1868 饥饿的奶牛。

P1868 饥饿的奶牛

题材叙述

发平等长条奶牛冲来了围栏,来到了一如既往处在圣地(对于奶牛来说),上面用牛语写着同样段子文字。

现用汉语翻译啊:

起N个区间,每个区间x,y表示提供的x~y共y-x+1堆放上牧草。你得挑选任意区间但不可知生双重的局部。

于奶牛来说,自然是藉的越多越好,然而奶牛智商有限,现在呼吁而帮忙他。

题材叙述

有一样久奶牛冲来了围栏,来到了相同处在圣地(对于奶牛来说),上面用牛语写在雷同段落文字。

现用汉语翻译为:

产生N个区间,每个区间x,y表示提供的x~y共y-x+1堆放上牧草。你得挑选任意区间但不克来再次的一对。

对奶牛来说,自然是藉的越多越好,然而奶牛智商有限,现在请而拉他。

输入输出格式

输入格式:

 

第一行,N,如题

连下去N行,每行一个数x,y,如题

 

出口格式:

 

一个屡,最多的距离数

 

输入输出格式

输入格式:

 

第一行,N,如题

连通下去N行,每行一个数x,y,如题

 

输出格式:

 

一个往往,最多之间隔数

 

输入输出样例

输入样例#1: 复制

3
1 3
7 8
3 4

新普京出口样例#1: 复制

5

输入输出样例

输入样例#1:

3
1 3
7 8
3 4

输出样例#1:

5

说明

1<=n<=150000

0<=x<=y<=3000000

 区间覆盖问题

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=3000009;
struct node{
    int L,R;
}a[N];
int n,mx;
bool cmp(node x,node y)
{    return x.L<y.L;}
int f[N],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].L,&a[i].R);
        mx=max(mx,a[i].R);
    }
    sort(a+1,a+1+n,cmp);
    int j=1;
    for(int i=0;i<=mx;i++)
    {
        f[i]=max(f[i],f[i-1]);
        while(a[j].L==i&&j<=n)
        {
            f[a[j].R]=max(f[a[j].R],f[a[j].L-1]+a[j].R-a[j].L+1);
            j++;
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

 

说明

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]);
}

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注