斜率优化dp练习

时间：2021-09-05 00:03:13

1.HDU3507

裸题，有助于理解斜率优化的精髓。

dp[i]=min(dp[j]+m+(sum[i]-sum[j])2)

很显然不是单调队列。

根据斜率优化的的定义，就是先设两个决策j,k

什么时候我们认为在 i 的环境下 j 比 k 好呢？根据上面的递推式，得到下面这么一个式子

dp[j]+m+(sum[i]-sum[j])2<dp[k]+m+(sum[i]-sum[k])2

打开括号：

dp[j]+m+sum[i]2+sum[j]2-2*sum[i]*sum[j]<dp[k]+m+sum[i]2+sum[k]2-2*sum[i]*sum[k]

移项，将有 i 的项移到右侧：

dp[j]+sum[j]2-dp[k]-sum[k]2<2*sum[i]*(sum[j]-sum[k])

除下来：

(dp[j]+sum[j]2-dp[k]-sum[k]2)/[2*(sum[j]-sum[k])]<sum[i]

好了这就是斜率了^_^

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 typedef long long lnt;
 5 int Q[1000000];
 6 lnt sum[1000000];
 7 lnt dp[1000000];
 8 int h,t;
 9 lnt n;
10 lnt m;
11 lnt X(int x)
12 {
13     return dp[x]+sum[x]*sum[x];
14 }
15 lnt tp(int i,int j)
16 {
17     return X(i)-X(j);
18 }
19 lnt btm(int i,int j)
20 {
21     return 2*sum[i]-2*sum[j];
22 }
23 int main()
24 {
25     while(scanf("%lld%lld",&n,&m)!=EOF)
26     {
27         sum[0]=0;
28         for(int i=1;i<=n;i++)
29             scanf("%lld",&sum[i]);
30         for(int i=1;i<=n;i++)
31             sum[i]+=sum[i-1];
32         h=t=1;
33         Q[1]=0;
34         dp[0]=0;
35         for(int i=1;i<=n;i++)
36         {
37             while(h<t&&(tp(Q[h+1],Q[h])<=sum[i]*btm(Q[h+1],Q[h])))
38                 h++;
39             dp[i]=dp[Q[h]]+m+(sum[i]-sum[Q[h]])*(sum[i]-sum[Q[h]]);
40             while(h<t&&(tp(Q[t],Q[t-1])*btm(i,Q[t])>=tp(i,Q[t])*btm(Q[t],Q[t-1])))
41                 t--;
42             Q[++t]=i;
43         }
44         printf("%lld\n",dp[n]);
45     }
46     return 0;
47 }

 2.BZOJ1010: [HNOI2008]玩具装箱toy

这道题依然斜率单调

dp方程自己推：

dp[i]=min(dp[j]+(i-j-1+sum[i]-sum[j]-L)2)

依然假设在 i 的环境下决策 j 优于 k 

那么：

dp[j]+(i-j-1+sum[i]-sum[j]-L)2<dp[k]+(i-k-1+sum[i]-sum[k]-L)2

将常数项与与 i 有关的项放到一起，展开：

(sum[j]+j)2-2*(i+sum[i]-L-1)*(sum[j]+j)+dp[j]<(sum[k]+k)2-2*(i+sum[i]-L-1)*(sum[k]+k)+dp[k]

设函数 f(x)=sum[x]+x , h(x)=x+sum[x]-L-1 , g(x)=dp[x]+f(x)2

得到当：

g(j)-g(k)<2*h(i)*(f(j)-f(k)) 时，j 比 k 优秀。

f(x)单调递增，斜率单调。

时间复杂度O(n)

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 typedef long long lnt;
 5 lnt sum[1000000];
 6 lnt dp[1000000];
 7 int Q[1000000];
 8 int h,t;
 9 int n;
10 lnt L;
11 lnt f(int x)
12 {
13     return (sum[x]+(lnt)(x));
14 }
15 lnt k(int x)
16 {
17     return ((lnt)(x)+sum[x]-L-1);
18 }
19 lnt g(int x)
20 {
21     return (dp[x]+f(x)*f(x));
22 }
23 lnt squ(lnt x)
24 {
25     return x*x;
26 }
27 int main()
28 {
29     scanf("%d%lld",&n,&L);
30     for(int i=1;i<=n;i++)
31     {
32         scanf("%lld",&sum[i]);
33         sum[i]+=sum[i-1];
34     }
35     Q[1]=0;
36     dp[0]=0;
37     h=t=1;
38     for(int i=1;i<=n;i++)
39     {
40         while(h<t&&g(Q[h+1])-g(Q[h])<2ll*k(i)*(f(Q[h+1])-f(Q[h])))
41             h++;
42         dp[i]=dp[Q[h]]+squ((lnt)(i-Q[h]-1)+sum[i]-sum[Q[h]]-L);
43         while(h<t&&(((g(Q[t-1])-g(Q[t]))*(f(Q[t])-f(i)))>((g(Q[t])-g(i))*(f(Q[t-1])-f(Q[t])))))
44             t--;
45         Q[++t]=i;
46     }
47     printf("%lld\n",dp[n]);
48     return 0;
49 }

 3.BZOJ1911: [Apio2010]特别行动队

斜率单调。

方程自己推：

设：g(x)=a*x2+b*x+c

dp[i]=max(dp[j]+g(sum[i]-sum[j]))

设在 i 环境下决策 j 优于 k

dp[j]+g(sum[i]-sum[j])>dp[k]+g(sum[i]-sum[k])

设f(x)=dp[x]+a*sum[x]2-b*sum[x]

则当：

f(j)-f(k)>2*a*sum[i]*(sum[j]-sum[k])

设 j > k 斜率单调

时间复杂度O(n)

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdio>
 4 typedef long long lnt;
 5 lnt sum[1000006];
 6 lnt dp[1000006];
 7 int Q[1000006];
 8 int h,t;
 9 int n;
10 lnt a,b,c;
11 lnt f(int x)
12 {
13     return dp[x]+a*sum[x]*sum[x]-b*sum[x];
14 }
15 lnt g(lnt x)
16 {
17     return a*x*x+b*x+c;
18 }
19 int main(void)
20 {
21     sum[0]=0;
22     h=t=1;
23     scanf("%d",&n);
24     scanf("%lld%lld%lld",&a,&b,&c);
25     for(int i=1;i<=n;i++)
26     {
27         scanf("%lld",&sum[i]);
28         sum[i]+=sum[i-1];
29     }
30     Q[1]=0;
31     dp[0]=0;
32     for(int i=1;i<=n;i++)
33     {
34         while(h<t&&(f(Q[h+1])-f(Q[h]))>2*a*sum[i]*(sum[Q[h+1]]-sum[Q[h]]))
35             h++;
36         dp[i]=dp[Q[h]]+g(sum[i]-sum[Q[h]]);
37         while(h<t&&(f(Q[t])-f(Q[t-1]))*(sum[i]-sum[Q[t]])<=(f(i)-f(Q[t]))*(sum[Q[t]]-sum[Q[t-1]]))
38             t--;
39         Q[++t]=i;
40     }
41     printf("%lld\n",dp[n]);
42     return 0;
43 }

 4.BZOJ4518: [Sdoi2016]征途

这次变成二维的了。

都一样，展开方程+斜率优化。

这次要对于每一天进行O(n)转移，共m天，时间复杂度O(n*m)

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 typedef long long lnt;
 5 lnt dp[4000][4000];
 6 lnt sum[10000];
 7 int Q[1000000];
 8 lnt n,m;
 9 lnt L;
10 int h,t;
11 lnt squ(lnt x)
12 {
13     return x*x;
14 }
15 lnt f(int x,int i)
16 {
17     return dp[x][i]+m*squ(sum[x])+2ll*L*sum[x];
18 }
19 int main()
20 {
21     scanf("%lld%lld",&n,&m);
22     for(int i=1;i<=n;i++)
23     {
24         scanf("%lld",&sum[i]);
25         sum[i]+=sum[i-1];
26     }
27     L=sum[n];
28     for(int i=1;i<=n;i++)
29     {
30         dp[i][1]=m*squ(sum[i])-2ll*L*sum[i];
31     }
32     for(int d=2;d<=m;d++)
33     {
34         t=h=1;
35         Q[1]=0;
36         for(int i=1;i<=n;i++)
37         {
38             while(h<t&&(f(Q[h+1],d-1)-f(Q[h],d-1))<2ll*m*sum[i]*(sum[Q[h+1]]-sum[Q[h]]))
39                 h++;
40             dp[i][d]=dp[Q[h]][d-1]+m*squ(sum[i]-sum[Q[h]])-2ll*L*(sum[i]-sum[Q[h]]);
41             while(h<t&&(f(Q[t],d-1)-f(Q[t-1],d-1))*(sum[i]-sum[Q[t]])>(f(i,d-1)-f(Q[t],d-1))*(sum[Q[t]]-sum[Q[t-1]]))
42                 t--;
43             Q[++t]=i;
44         }
45     }
46     printf("%lld\n",dp[n][m]+squ(L));
47     return 0;
48 }

 

标签：

相关文章