Print Article
time limit per test 3 second memory limit per test 256 megabytes
Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
(Ci的和)^2+M

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

传送门:HDU3507

Input

There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

Output

A single number, meaning the mininum cost to print the article.

Sample Input

1
2
3
4
5
6
5 5
5
9
5
7
5

Sample Output

1
230

题解

斜率DP的入门题。 题意很清楚,就是输出序列a[n],每连续输出的费用是连续输出的数字和的平方加上常数M 让我们求这个费用的最小值。 设dp[i]表示输出前i个的最小费用 dp[i]= min(dp[j]+(sum[i]-sum[j])^2 +M) 0小于j小于i 但这样O(n^2)会超时 推荐blog:http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html 要注意的是每次对队头和队尾的维护操作 sum[i]是递增的 kuangbin大大写的第一种情况即队头的操作很好理解 但要注意的是第二种对队尾的操作 要严格保持队列里的单调性
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.*;  
import java.util.*;
public class Main {
static long[]sum;
static long[]shu;
static long[]dp;
static int m;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
m=sc.nextInt();
sum=new long[n+1];
shu=new long[n+1];
for(int i=1;i<=n;i++){
shu[i]=sc.nextInt();
sum[i]=sum[i-1]+shu[i];
}
dp=new long[n+1];
dp[0]=0;
ArrayList<Integer>list=new ArrayList<Integer>();
//Deque<Integer>queue=new LinkedList<Integer>();
list.add(0);
for(int i=1;i<=n;i++){
while(list.size()>=2&&(calleft(list.get(1),list.get(0))<=sum[i]*calright(list.get(1),list.get(0)))){
list.remove(0);
}
dp[i]=getdp(list.get(0),i);
while(list.size()>=2){
int t=list.size()-1;
long l1=calleft(list.get(t),list.get(t-1));
long r1=calright(list.get(t),list.get(t-1));
long l2=calleft(i,list.get(t));
long r2=calright(i,list.get(t));
if(l1*r2>=l2*r1) list.remove(list.size()-1);
else break;
}
list.add(i);
}
pw.println(dp[n]);
pw.flush();
}

}
static long getdp(int j,int i){
return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
static long calleft(int a,int b){
return calup(a)-calup(b);
}
static long calright(int a,int b){
return caldown(a)-caldown(b);
}
static long calup(int index){
return dp[index]+sum[index]*sum[index];
}
static long caldown(int index){
return 2*sum[index];
}
}