CF1932(div3)题解

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";
  }