职务地址:http :// www . lydsy . com / JudgeOnline / problem . php ? id = 1010

题目大意:见原题。

算法分析:

设s[i]为c[i]的前缀和,f[i]表示第1个物品到第i个物品的最小代价。

易得DP方程为f[i]=min(f[j]+(s[i]-s[j]+i-j+1-l)^2)。

设t[i]=s[i]+i。则f[i]=min(f[j]+(t[i]-t[j]+1-l)^2。

设m=t[i]-l-1。则f[i]=min(f[j]+(m-t[j])^2)。

对i做决策时,设j,k为2个一般的决策点。设j<k。

若k比j优,则有

f[k]+(m-t[k])^2<f[j]+(m-t[j])^2

展开,得

f[k]+m^2-2*m*t[k]+t[k]^2<f[j]+m^2-2*m*t[j]+t[j]^2

化简,得

((f[k]+t[k]^2)-(f[j]+t[j]^2))/(t[k]-t[j])<2*m=2*(s[i]+i-l-1)

于是能够用单调队列来优化DP。

单调队列优化DP的伪代码:

for (int i=1;i<=n;++i){
while (h+1<t && slope(q[h],q[h+1])<...) h++;
f[i]=...;
while (h+1<t && slope(q[t-2],q[t-1])>slope(q[t-1],i)) t--;
q[t++]=i;
}

斜率优化的2个重要结论(对于此题):

1)j<k,若slope(j,k)<2*(s[i]+i-l-1),则k比j优。

(PS:不等式左边为仅仅与j,k有关的式子。不等式右边为仅仅与i有关的式子)

2)j<k<l,若slope(j,k)>slope(k,l),则k能够被舍去。

Code:

#include <cstdio>

#define N 50000

using namespace std;

int n,l,h,t=1,c[N+10],q[N+10];
long long s[N+10],f[N+10]; template <typename T>
inline T sqr(T x){return x*x;}
inline double slope(int i,int j){return (f[i]+sqr((double)s[i]+i)-f[j]-sqr((double)s[j]+j))/(s[i]+i-s[j]-j);} int main(){
#ifndef ONLINE_JUDGE
freopen("1010.in","r",stdin);
freopen("1010.out","w",stdout);
#endif
scanf("%d%d",&n,&l);
for (int i=1;i<=n;++i) scanf("%d",&c[i]);
for (int i=1;i<=n;++i) s[i]=s[i-1]+c[i];
for (int i=1;i<=n;++i){
while (h+1<t && slope(q[h],q[h+1])<2*(s[i]+i-l-1)) h++;
f[i]=f[q[h]]+sqr(s[i]-s[q[h]]+i-q[h]-1-l);
while (h+1<t && slope(q[t-2],q[t-1])>slope(q[t-1],i)) t--;
q[t++]=i;
}
printf("%lld\n",f[n]);
return 0;
}

By Charlie Pan

Jul 18,2014

版权声明:本文博客原创文章。博客,未经同意,不得转载。

05-04 05:30