【BZOJ3675】【APIO2014】序列分割
wangyuchen
2018-03-22 16:39:47
## 题目：
[题目在这里](http://www.lydsy.com/JudgeOnline/problem.php?id=3675)
## 思路:
这题的DP不难， 但不要被题目描述迷惑了
状态转移方程:
$f_i = min \{ g_j + (sum_i - sum_j) * sum_j \}$
(用了滚动数组, f是当前处理的， g是上一次得出的)
可以用斜率优化
$g_j + (sum_i - sum_j) * sum_j >= g_k + (sum_i -sum_k) * sum_k$
$g_j - g_k - {sum_j}^2 + {sum_k}^2 >= sum_i * (sum_k - sum_j)$
${g_j - g_k - {sum_j}^2 + {sum_k}^2 \over (sum_k - sum_j)} >= sum_i$
```cpp
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
inline long long sqr(long long x) { return x * x; }
long long a[N];
long long sum[N];
long long g[N], f[N];
int Q[N], hd, tl;
double calc(int j, int k) { return (double)(g[j]-g[k]+sqr(sum[k])-sqr(sum[j])) / (double)(sum[k]-sum[j]); }
int main()
{ int n, m;
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++)
scanf("%lld", &a[i]);
int tot = 0;
for(int i=1; i<=n; i++)
if(a[i] != 0) a[++tot] = a[i];
n = tot;
for(int i=1; i<=n; i++)
sum[i] = sum[i-1] + a[i];
for(int i=1; i<=m; i++)
{ hd = tl = 0;
for(int j=i; j<=n; j++)
{ while(hd < tl-1 && calc(Q[hd], Q[hd+1]) <= sum[j]) hd++;
f[j] = g[Q[hd]] + sum[Q[hd]] * (sum[j]-sum[Q[hd]]);
while(hd < tl-1 && calc(Q[tl-1], j) <= calc(Q[tl-2], Q[tl-1])) tl--;
Q[tl++] = j;
}
for(int j=i; j<=n; j++) swap(f[j], g[j]);
}
printf("%lld\n", g[n]);
return 0;
}
```