hdu3507 Print Article DP+斜率优化

题意：就是给一个序列，让你分成很多段，每段按照题目的公式算出答案，要所有的答案加起来最小

思路一：（参考）http://www.cnblogs.com/lidaxin/p/5116577.html

斜率优化。
设f[i]表示前i个数分段后的最小值,则转移式为f[i]=min{f[j]+(sum[i]-sum[j])^2+M}，1<=j<i
进一步得:f[i]=min{ (f[j]+sum[j]^2-2*sum[i]*sum[j])+(sum[i]^2+M) }

设y(j)=f[j]+sum[j]^2，a[i]=sum[i]，x(j)=sum(j)，则f[i]=min{y(j)-2*a[i]*x(j)}+sum[i]^2+M

则要求min p=y+2ax , 单调队列维护下凸包。

1 while(L<R && q[L+1].y-2*sum[i]*q[L+1].x <= q[L].y-2*sum[i]*q[L].x) L++;
2 now.x = sum[i];
3 now.y = q[L].y-2*sum[i]*q[L].x+2*sum[i]*sum[i]+m;
4 while(L<R && cross(q[R-1],q[R],now)<=0) R--;
5 q[++R] = now;

now.y = y[i] = f[i]+sum[j]^2 = min{ (f[j]+sum[j]^2-2*sum[i]*sum[j])+(sum[i]^2+M) } + sum[i]^2

答案就是 y[n]=q[R].y=f[n]+sum[n]^2 ==> q[R].y-sum[n]^2；

代码一：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define mp(x,y) make_pair(x,y)
 6 const int maxn = 5e5+10;
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 int n,m,a;
17 int sum[maxn];
18 
19 struct node{
20     int x,y;
21 }now,q[maxn];
22 
23 int cross(node A,node B,node sum){
24     return (B.x-A.x)*(sum.y-A.y) - (sum.x-A.x)*(B.y-A.y);
25 }
26 
27 int main(){
28     while(scanf("%d%d",&n,&m)==2){
29         mem(sum);
30         for(int i=1; i<=n; i++){
31             scanf("%d",&a);
32             sum[i] = sum[i-1]+a;
33         }
34 
35         int L=0,R=0;
36         for(int i=1; i<=n; i++){
37             while(L<R && q[L+1].y-2*sum[i]*q[L+1].x <= q[L].y-2*sum[i]*q[L].x) L++;
38             now.x = sum[i];
39             now.y = q[L].y-2*sum[i]*q[L].x+2*sum[i]*sum[i]+m;
40             while(L<R && cross(q[R-1],q[R],now)<=0) R--;
41             q[++R] = now;
42         }
43 
44         printf("%d
",q[R].y-sum[n]*sum[n]);
45     }
46 
47     return 0;
48 }

思路二：参考：http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html

kuangbin大神= = 非常详细

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define mp(x,y) make_pair(x,y)
 6 const int maxn = 5e5+10;
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 
17 int n,m;
18 int sum[maxn],f[maxn],q[maxn];
19 
20 // int slope(int j,int k){ // WA!!! 
21 //     return ((double)(f[j]+sum[j]*sum[j]-(f[k]+sum[k]*sum[k]))) / ((double)(2*(sum[j]-sum[k])));
22 // }
23 
24 int getUP(int j,int k)
25 {
26     return f[j]+sum[j]*sum[j]-(f[k]+sum[k]*sum[k]);
27 }
28 int getDOWN(int j,int  k)
29 {
30     return 2*(sum[j]-sum[k]);
31 }
32 
33 int main(){
34     //f[i]=min((sum[i]-sum[j])^2+m+f[j])
35     while(scanf("%d%d",&n,&m)==2){
36         sum[0],f[0]=0;q[0]=0;
37         for(int i=1; i<=n; i++){
38             int a; scanf("%d",&a);
39             sum[i] = sum[i-1]+a;
40         }
41 
42         int L=0,R=0;
43         for(int i=1; i<=n; i++){
44             while(L<R && getUP(q[L+1],q[L]) <= sum[i]*getDOWN(q[L+1],q[L])) 
45                 L++;
46             int j = q[L];
47             f[i] = f[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + m;
48             while(L<R && (getUP(i,q[R])*getDOWN(q[R],q[R-1]) <= getUP(q[R],q[R-1])*getDOWN(i,q[R]))) 
49                 R--;
50             q[++R] = i;
51         }
52 
53         // int L=0,R=0;
54         // for(int i=1; i<=n; i++){
55         //     while(L<R && slope(q[L+1],q[L]) <= sum[i]) L++;
56         //     int j = q[L];
57         //     f[i] = f[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + m;
58         //     while(L<R && slope(i,q[R]) <= slope(q[R],q[R-1])) R--;
59         //     q[++R] = i;
60         // }
61         printf("%d
",f[n]);
62     }
63 
64     return 0;
65 }