求助水题
查看原帖
求助水题
315205
Kniqht楼主2021/8/23 16:02

rt ,我跟我看到的题解状态设的都不一样,请问f[i]表示前i个区间最多能吃到的牧草堆数这个状态可以吗?还是我想错了?

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+1;
int n,f[N];
struct Node{
    int l,r;
}a[N];
bool cmp(Node x,Node y){
    if(x.l!=y.l) return x.l<y.l;
    else return x.r<y.r;
}
int main(){
    int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]+(a[i-1].r>=a[i].l?0:a[i].r-a[i].l+1);
        int j=i-1;
        while(a[j].r>=a[i].l){
            j--;
            f[i]=max(f[i],f[j]+a[i].r-a[i].l+1);
        }
        ans=max(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}


2021/8/23 16:02
加载中...