发布时间：2024-02-19

F - Feed Cats

题意： 有多个区间，每个区间内只能选一个点，问最多可以选择多少个区间
思路：
考虑dp

• 差分，然后算前缀和可以判断选择当前点的贡献
• 预处理选择当前点后最右边的不能选的点
• $不选i,则dp_i=max(dp_i,dp_{i-1})$
• $选i,则dp_{R_i+1}=max(dp_{R_i+1},dp_i+cnt)$
• $答案为dp_{n+1}$

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> b(n+10),dp(n+10),R(n+10);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        b[l]++;
        b[r+1]--;
        R[l]=max(R[l],r);
    }
    for(int i=1;i<=n;i++)R[i]=max(R[i],R[i-1]);
    int cnt=0;
    for(int i=1;i<=n+1;i++){
        cnt+=b[i];
        dp[i]=max(dp[i],dp[i-1]);
        if(R[i])dp[R[i]+1]=max(dp[R[i]+1],dp[i]+cnt);
    }
    cout<<dp[n+1]<<"\n";
}