啊,这个是我很早很早之前就想搞懂的知识点了emmm可是一直没有解决。今天总算有机会了!
我今天打算做P3195,把这道板子肝出来。
题意:
你有一个序列,你可以任意地将其中的i-j项合并成一组。并且对于每一组,代价为 $(x-L)^2$。其中, $x=j-i+\sum_{k=i}^j C_k$,L为常亮。求最小代价。
$N^2$ 解法
我们让 $s[i]=\sum_{j=1}^i+i$(即前缀和+i),可以发现状态转移方程可以变成:
$$f[i]=min_{j=0}^{i-1}(f[j]+(s[i]-s[j]-1-l)^2);$$
于是愉快 $N^2$暴力,吸氧后70分。
午餐
午餐和Atalod一起吃,吃了金拱门。虽然等了很久,但是我们聊了一会儿斜率优化。
斜优数论证明
对于上面的这个方程,我们假设对于一个我们将要求的i。有两个j,分别是 $j_1,j_2$,我们假设 $j_1$的解更小(更优秀)。
$$f[j_1]+(s_i-s_{j_1}-1-l)^2\leq f[j_2]+(s_i-s_{j_2}-1-l)^2$$
拆开:
$$f[j_1]+s_i^2-2*s_i*(s_{j_1}-1-l)+(s_{j_1}-1-l)^2\leq f[j_2]+s_i^2-2*s_i*(s_{j_2}-1-l)+(s_{j_2}-1-l)^2$$
化简:
$$-2*s_i*(s_{j_1}-1-l)+2*s_i*(s_{j_2}-1-l)\leq -f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2$$
再化简:
$$2*s_i*(s_{j_2}-s_{j_1})\leq -f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2$$
再再化简:
$$2*s_i\leq \frac{-f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2}{(s_{j_2}-s_{j_1})}$$
经过我们的推导,我们发现,只要任意的 $j_1,j_2$满足上式子, $j_1$就更优秀,也就是 $j_1$更小。 接下来,我们发现,我们可以根据下标与下标所对应的值建立一个个散点。
根据我们的推论, $2*s_i$作为斜率,我们应当找到某个j作为转移决策点,而且这个转移决策点需要保证让 $f[i]$最小。
借用上面的一个公式: $$f[i]=f[j]+(s[i]-s[j]-1-l)^2;$$
$f[j]$就是高度, $(s[i]-s[j]-1-l)^2$是斜率
然后发现我们要做的只是拿一条斜率为 $2*s[i]$的直线去逼近它,找到第一个决策点。
我们可以发现,只有这些散点中能够成下凸壳的那些点才有可能成为决策点。
然后队列或者栈维护凸壳。
而这个方程,前缀和单增,y=x单增,所以 $s_i$单增,所以斜率单增,满足斜率单调性。
对于有决策单调性的方程,决策点一定会会后移或不动,不可能前移。每个点是最多进队一次,出队一次。复杂度 $O(n)$
对于没有决策单调性的点,决策点可能乱跳。每个点进栈出栈最多一次。对于每一个i,在凸壳上二分即可找到决策点。复杂度 $O(n log n)$
此题吸氧70分的 $O(n^2)$做法
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52505;
int f[N],a[N],s[N];
int q[N],be,ed;
int n,l;
int X(int j){
return s[j];
}
int Y(int j){
return f[j]+(s[j]+l)*(s[j]+l);
}
long double slope(int i,int j){
return (long double)(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
cin>>n>>l;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i]+1;
}
q[++ed]=1;
for(int i=1;i<=n;++i){
f[i]=0x3f3f3f3f3f3f3f3f;
for(int j=0;j<i;++j)
f[i]=min(f[i],f[j]+(s[i]-s[j]-1-l)*(s[i]-s[j]-1-l));
}
cout<<f[n];
}
斜优 $O(n)$做法
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52505;
int f[N],a[N],s[N];
int q[N],be,ed;
int n,l;
int X(int j){
return s[j];
}
int Y(int j){
return f[j]+(s[j]+l)*(s[j]+l);
}
long double slope(int i,int j){
return (long double)(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
cin>>n>>l;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i]+1;
}
q[++ed]=1;
for(int i=1;i<=n;++i){
// f[i]=0x3f3f3f3f3f3f3f3f;
// for(int j=0;j<i;++j)
// f[i]=min(f[i],f[j]+(s[i]-s[j]-1-l)*(s[i]-s[j]-1-l));
while(be<=ed&&slope(q[be],q[be+1])<=2*s[i])
be++;
f[i]=f[q[be]]+(s[i]-s[q[be]]-1-l)*(s[i]-s[q[be]]-1-l);
while(be<=ed&&slope(q[ed-1],q[ed])>=slope(q[ed-1],i))
ed--;
q[++ed]=i;
}
cout<<f[n];
}