翻译
有一条无限长的数轴
上面放着n个布丁
相邻两个布丁会黏在一起，移动任意一块另外一块也会移动
每次你可以向左或者向右移动一块布丁，这块布丁会一直运动到撞到一块布丁为止
然后他们就黏在一起了
数轴上有m个特殊点
你可以做无数次操作，求最多能覆盖多少个特殊点
n<=100000,m<=2000
题解
容易发现，最后布丁一定会分成一段一段的
其中每一段的左边或者右边一定有一个没有动过的布丁
然后就可以dp辣
设f[i]表示前i个布丁能覆盖的特殊点数量
预处理每个布丁往左第一个与往右第一个的特殊点，不包括与自己重合的
遇到每个布丁，枚举他往左往右覆盖多少个特殊点，容易得到需要多少个布丁来覆盖他们
直接转移即可
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline int read() {
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
write(x);printf(" ");} int n,m; int f[100005][2];//在自己位置 不在自己位置 int a[100005],b[2005]; int pre[100005],nxt[100005]; int fir[100005],ed[100005]; int main() {
freopen("a.in","r",stdin);freopen("a.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=m;i++)b[i]=read();sort(a+1,a+1+n);sort(b+1,b+1+m);fir[1]=1;for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]+1)fir[i]=i;else fir[i]=fir[i-1];}for(int i=n;i>=1;i--){
if(a[i]!=a[i+1]-1)ed[i]=i;else ed[i]=ed[i+1];}for(int i=1,j=0;i<=n;i++){
while(b[j+1]<a[i]&&j<m)j++;pre[i]=j;}for(int i=n,j=m+1;i>=1;i--){
while(b[j-1]>a[i]&&j>1)j--;nxt[i]=j;}for(int i=1;i<=n;i++){
if(fir[i]==fir[i-1]&&ed[i]==ed[i+1])continue;f[i][0]=max(f[i][0],max(f[fir[i]-1][0],f[fir[i]-1][1]));for(int j=1;j<=m;j++){
int pa=pre[i]-j+1;//第j个奇怪格子的编号 if(pa<=0)break;int pos=a[i]-b[pa];//需要这么多个布丁怪if(pos>i)break;int gg=fir[i-pos];//凑够这么多个布丁怪的编号if(gg<=0)break;f[i][0]=max(f[i][0],max(f[gg-1][0],f[gg-1][1])+j); }if(b[nxt[i]-1]==a[i])f[i][0]++;for(int j=1;j<=m;j++){
int pa=nxt[i]+j-1;if(pa>m)break;int pos=b[pa]-a[i];if(pos>n-i)break;int gg=ed[i+pos];if(gg>n)break;f[gg][1]=max(f[gg][1],f[i][0]+j);if(a[gg]-a[i]+1==j)f[gg][0]=max(f[gg][0],f[i][0]+j);}}printf("%d\n",max(f[n][0],f[n][1]));return 0; }```