2014
04-09

# Print Article

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

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

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.

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.

5 5
5
9
5
7
5

230

状态转移方程为: dp[i] = min(dp[j] + (sum[i]-sum[j])^2 + m) (j < i);

方法一：dp[i] = dp[j] + (sum[i]-sum[j])^2 + m = dp[j] + sum[i] * sum[i] + sum[j] * sum[j] – 2 * sum[i] * sum[j] + m;

设y =  dp[j] + sum[j] * sum[j],x = sum[j]，那么原式等于:dp[i] = y + 2 * sum[i] * x + m + sum[i] * sum[i],然后套下斜率优化DP模板即可ac。

方法二:方法二使用的优化技巧类似于四边形不等式，用个s[i] 记录dp[i]由前面的哪个状态转移过来，然后枚举的时候只要枚举s[i-1] 到i-1就可以了。

第二种方法似乎比第一种要慢一些，常数比较大。

Input
5 5
5 9 5 7 5
1 1000
1
3 1000
1 3 5
3 0
1 3 5
1 0
100000

OutPut:
230
1001
1081
35
10000000000

C艹代码：

#include <stdio.h>
#include <string.h>
#define MAX 510000
#define int64 long long

struct point{

int64 x,y,c;
}pot[MAX];
int n,m,arr[MAX];
int64 sum[MAX],dp[MAX];

int CheckIt(int x,int y,int z) {

point p0 = pot[x],p1 = pot[y],p2 = pot[z];
return (p0.x -p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) <= 0;
}
int NotBest(int x,int y,int k) {

point p0 = pot[x],p1 = pot[y];
return p0.y - k * p0.x > p1.y - k * p1.x;
}
int64 Solve_DP() {

qu[tail] = 0;
pot[0].x = pot[0].y = 0;

for (int i = 1; i <= n; ++i) {

pot[i].x = sum[i-1];
pot[i].y = dp[i-1] + sum[i-1] * sum[i-1];
while (head <= tail - 1 &&
CheckIt(qu[tail-1],qu[tail],i)) tail--;

qu[++tail] = i;
while (head + 1 <= tail &&
dp[i] = pot[k].y - 2 * sum[i] * pot[k].x + sum[i] * sum[i] + m;
}

return dp[n];
}
int64 Solve_DP2() {

for (int64 mmin,i = 1; i <= n; ++i) {

mmin = -1;
for (int j = qu[i-1]; j < i; ++j)
if (mmin == -1 ||
dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) < mmin) {

mmin = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]);
qu[i] = j;
}

dp[i] = mmin + m;
}
return dp[n];
}

int main()
{
int i,j,k;

while (scanf("%d%d",&n,&m) != EOF) {

for (i = 1; i <= n; ++i)
scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];

int64 ans = Solve_DP2();
printf("%lld\n",ans);
}
}

1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}