1 条题解

  • 0
    @ 2025-10-8 16:48:48
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+10;
    template<typename T>void qr(T& x)
    {
    	x=0;int f=1;char c=getchar();
    	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
    	for( ; isdigit(c);c=getchar())x=x*10+c-48;
    	x=x*f;
    }
    struct node{int x,y,L;}a[N];
    int n,f[N];
    int find(int x)
    {
    	int L=1,R=n,mid,ans=0;
    	while(L<=R)
    	{
    		mid=(L+R)>>1; 
    		if(a[mid].y<=x)L=mid+1,ans=mid;
    		else R=mid-1;
    	}
    	return ans;
    }
    int main()
    {
        qr(n);
        for(int i=1;i<=n;i++)
        {
            qr(a[i].x);qr(a[i].y);
    		a[i].L=a[i].y-a[i].x;
        }
        sort(a+1,a+n+1,[](const node &n1,const node &n2){return n1.y<n2.y;});
        memset(f,0,sizeof(f));
        a[0]={0,0};
    	int ans=0;
        for(int i=1;i<=n;i++)
        {
        	f[i]=f[i-1];
        	int j=find(a[i].x);
            f[i]=max(f[i],f[j]+a[i].L);
            ans=max(ans,f[i]);
        }
        printf("%d\n",ans);
        return 0;
    }
    
    • 1

    *【动态规划:状态设计DP】不重叠线段的最大长度和[scy]

    信息

    ID
    246
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    138
    已通过
    49
    上传者