题解
每个点要么喂,要么不喂,我们令 \(dp[i]\) 为前 \(i\) 个步骤最多能喂养多少猫,易得 \(dp[i]\) 是单调不减的
我们再维护每个点被包含的区间里的最左端 \(l\)
这样一来 \(dp[i]=max(dp[i-1],dp[l-1]+sum)\)
可是如何维护每个点被包含区间的最左端呢?
我们先记录下每个右端点的最小左端点,然后逆序遍历,即对于 \(i\) 求以 \([i,n]\) 内为右端点的最小左端点
code
#include<bits/stdc++.h>
using namespace std;
int farl[2000005],pre[1000006]={0},dp[1000006];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
farl[i]=n+1;
pre[i]=0;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
pre[x]++;
pre[y+1]--;
farl[y]=min(farl[y],x);
}
for(int i=n-1;i>=1;i--) farl[i]=min(farl[i],farl[i+1]);
int sum=0,ans=0;
for(int i=1;i<=n;i++)
{
sum+=pre[i];
dp[i]=dp[i-1];
if(farl[i]<=i) dp[i]=max(dp[i],dp[farl[i]-1]+sum);
ans=max(ans,dp[i]);
}
cout<<ans<<'\n';
}
return 0;
}
标签:Feed,pre,int,farl,--,Cats,端点,dp
From: https://www.cnblogs.com/pure4knowledge/p/18288219