学不动了，做到dp都不顺利QWQ。
Solution
可以证明：切的顺序和答案无关。
伪证明：对于最后块为$a,b,c$的切法共三种：
$$
\begin{aligned}
1.&(a+b)c+ab=ac+ab+bc \\
2.&(a+c)b+ac=ac+ab+bc
\end{aligned}
$$
然后推广（本人数学不太好，只会找规律）
然后dp方程就显然了：
$$
f[i][k]=f[j][k-1]+sj，s[i]= \sum_1^ia[i]
$$
观察数据范围发现无法通过此题。
考虑优化：因为下一层的答案一定只可能由本层推出，所以令本层的答案为：$g[i]$，下一层的答案：$f[i]$。
当对于i来说取j比取k优秀时：
$$
\begin{aligned}
&g[j]+sj>g[k]+sk\\
&\frac{g[j]-s[j]*s[j]-(g[k]-s[k]*s[k])}{-s[j]-(-s[k])}>s[i]
\end{aligned}
$$
所以每个点都可以表示为：$(-s[j],g[j]-s[j]*s[j])$。
用斜率优化即可。
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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000 + 5, M = 1e6 + 5, Inf = 1e9 + 7;
const double eps = 1e-8;
int n, m;
int a[N];
LL g[N], f[N], hh = 1, tt = 0, q[N];
LL s[N];
double get_k(int x, int y)
{
LL y1 = g[x] - s[x] * s[x], y2 = g[y] - s[y] * s[y];
LL x1 = -s[x], x2 = -s[y];
if(x1 == x2) return - Inf;
return (y1 - y2) / (double)(x1 - x2);
}
int from[205][N];
int ans;
int compare(double x, double y)
{
if(fabs(x - y) < eps) return 0;
if(x < y) return -1;
return 1;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
for(int i = 1;i <= n;i ++) s[i] = s[i - 1] + a[i];
for(int k = 1;k <= m;k ++)
{
for(int i = 1;i <= n;i ++) g[i] = f[i];
hh = 1, tt = 1;
for(int i = 1;i <= n;i ++)
{
while(hh < tt && compare(get_k(q[hh], q[hh + 1]), s[i]) != 1) hh ++;
from[k][i] = q[hh];
f[i] = g[q[hh]] + s[i] * s[q[hh]] - s[q[hh]] * s[q[hh]];
while(hh < tt && compare(get_k(q[tt], q[tt - 1]), get_k(q[tt - 1], i)) != -1) tt --;
q[++ tt] = i;
}
}
printf("%lld\n", f[n]);
ans = n;
for(int i = m;i >= 1;i --)
{
printf("%d ", from[i][ans]);
ans = from[i][ans];
}
return 0;
}
|