E. Two Platforms
读完题 发现好像跟y坐标没关系
考虑dp
dp[i][0/1/2]表示以第i个点结尾的用了0/1/2个板子的max
显然我们对于0我们都是初始化为0
对于dp[i][1]我们直接dp[i-k][0]+区间[i-k,i]点的个数
对于dp[i][2]我们显然相交不会是最优解 而且会算重复
dp[i-k-1][1]+区间[i-k,i]点的个数
因为坐标轴范围有1e9我们要离散化 然后算区间点的个数直接二分下标就好了
int dp[N][3],n,k;
vector<int>a;
int find(int x) {return lower_bound(all(a), x) - a.begin();}
void solve(){
cin>>n>>k;
vector<int>b(n+10);
a.resize(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
sort(all(a));
for(int i=0;i<=n;i++)for(int j=0;j<3;j++)dp[i][j]=0;
for(int i=0;i<a.size();i++){
dp[i][1]=max(dp[max(0ll,i-1)][1],dp[find(a[i]-k)][0]+i-find(a[i]-k)+1);
if(find(a[i]-k))dp[i][2]=max(dp[max(0ll,i-1)][2],dp[find(a[i]-k)-1][1]+i-find(a[i]-k)+1);
}
cout<<max(dp[a.size()-1][1],dp[a.size()-1][2])<<endl;
}
标签:667,个数,Codeforces,int,Div,dp
From: https://www.cnblogs.com/ycllz/p/16847364.html