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 }