猫猫cpu的缓存(NW)
在做 dp 的时候经常在某个细节处死扣,总的说还是没把握住题目的特征性和 dp 的整体架构。既然能一眼看出来是 dp 题,当根据题目特征列出个常规的 dp 式子,之后才有优化的资本。这是一般 dp 题的流程,重点在列出像样的 dp 式子,写一大坨不可用也不可优化的极端、特殊式子是没有意义的,要在把握 dp 的线性的基础上尝试状态转移,才能将千奇百怪的 dp 题化归成一套有迹可循的系统和模型。
读原题面,叽里呱啦写了千把字,结果最后一行给了下面这段话(
简而言之:
给你 m 个 1 到 n 之间的整数,你要找到若干个大小为固定的 k 的闭区间,使得所有这些数都在你找到的某个区间内。你需要最小化这些区间的并集的大小,并输出此大小。本题里区间/区间并集的大小,被定义为,这个区间/区间并集里整数的个数。
1
≤
k
≤
n
≤
1
0
9
,
1
≤
m
≤
3
⋅
1
0
5
,
p
i
≤
n
1\le k\le n\le 10^9,1\le m\le 3\cdot 10^5,p_i\le n
1≤k≤n≤109,1≤m≤3⋅105,pi≤n 且互不相同。
考场做法
考场上做 dp 题时脑子很乱,到最后实在不行推出来也推出一个很乱的式子,只过了两个样例,显然地暴毙,挂光光了,说明一开始思路的走向就不对。以后开头的推理要更加谨慎,开头思路歪后面很难跳出来。
这是考场的代码, f i , 0 / 1 f_{i,0/1} fi,0/1 表示 i i i 当开头(结尾)时囊括前 i i i 个点的最小值。自己看了都绷不住。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,k,m,p[N],f[N][2],l[N];
int main(){
freopen("cpu.in","r",stdin);
freopen("cpu.out","w",stdout);
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;i++) scanf("%d",p+i);
sort(p+1,p+m+1);
if(n-p[1]+1<=k||m==1) return printf("%d",k),0;
l[0]=1;
for(int i=1,L=1;i<=m;i++){
while (p[i]-p[L]>=k) L++;
l[i]=L;
}
// for(int i=1;i<=m;i++) printf("%d ",l[i]);puts("");
memset(f,0x3f,sizeof(f));
f[1][0]=k;if(p[1]>=k) f[1][1]=k;
for(int i=2;i<=m;i++){
if(n-p[i]+1>=k) f[i][0]=min(f[i-1][1]+k,f[l[i-1]][0]+max(0,p[i]-p[l[i-1]]));
if(p[i]>=k) f[i][1]=min(f[l[i]-1][1]+k,f[l[l[i]-1]][0]+max(0,p[i]-p[l[l[i]-1]]-k+1));
// printf("%d %d\n",f[i][0],f[i][1]);
}
printf("%d",f[m][1]);
return 0;
}
正解
注意题目特征,张超老师说想出第一个部分分就接近正解了。第一个部分分
O
(
2
n
⋅
n
)
O(2^n\cdot n)
O(2n⋅n),重要在于怎么判断一个序列是否合法:
m
m
m 个点包含是必然的,注意到题目的特征性,只要保证每个选下的区间长度都大于等于
k
k
k 即可。
类似的题目还有[USACO18JAN] Stamp Painting G。
对
p
p
p 排序是显然的。
所以我们设
f
i
f_i
fi 表示把前
i
i
i 个要囊括的点囊括需要的区间长度最小值,由于两个距离小于
k
k
k 的
p
i
,
p
j
p_i,p_j
pi,pj 转移方法不同,可以先考虑距离大于
k
k
k 的
p
i
,
p
j
p_i,p_j
pi,pj 如何转移,可以列出:
f
i
=
min
j
=
1
p
o
s
(
f
j
−
1
+
p
i
−
p
j
+
1
)
f_i=\min_{j=1}^{pos}(f_{j-1}+p_i-p_j+1)
fi=minj=1pos(fj−1+pi−pj+1),其中
p
o
s
pos
pos 是
i
i
i 往前第一个满足
p
i
−
p
j
≥
k
p_i-p_j\ge k
pi−pj≥k 的位置。
抽离无关量,得
f
i
=
p
i
+
1
+
min
j
=
1
p
o
s
(
f
j
−
1
−
p
j
)
f_i=p_i+1+\min_{j=1}^{pos}(f_{j-1}-p_j)
fi=pi+1+minj=1pos(fj−1−pj)
显然 p o s pos pos 单调不降,故 i i i 单增过程中 j j j 的范围只增不减,尺取不断取 min \min min 即可。
对于距离小于 k k k 的两点,只会在 p i p_i pi 和 p p o s + 1 p_{pos+1} ppos+1 时对答案产生贡献,增量为 k k k。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,k,m,p[N],f[N],w=0,mn=1e9;
int main(){
freopen("cpu.in","r",stdin);
freopen("cpu.out","w",stdout);
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;i++) scanf("%d",p+i);
sort(p+1,p+m+1);
for(int i=1;i<=m;i++){
while (p[i]-p[w+1]>=k) mn=min(mn,f[w]-p[++w]);
f[i]=min(p[i]+1+mn,f[w]+k);
}
printf("%d",f[m]);
}
总的来说,要把握住 dp 的常态化思路,抓题目特征,列可行性强的状态,状态转移,最后考虑优化。