【【UOJ|【UOJ #104】【APIO 2014】Split the sequence】http://uoj.ac/problem/104
此题的重点是答案只与切割的最终形态有关，与切割顺序无关。
设\(f(i,j)\)表示前\(i\)个元素切成\(j\)个能产生的最大贡献。
\(f(i,j)=\max\{f(k,j-1)+sum(k+1,i)(sum(1,n)-sum(k+1,i)),k 有决策点\(k\)和\(l\)，当\(k 可以把每个决策点\(k\)看成横坐标为\(sum_k\)，纵坐标为\(f(l,j-1)-sum_nsum_l-sum_l^2\)的点，每次用斜率为\(-2sum_i\)的直线平移到这个点上，找纵截距最大的直线经过的点作为决策点。
决策点一定在上凸壳，因为\(sum_i\)单调不降，用单调栈维护上凸壳即可。
又因为\(-2sum_i\)单调不升，具有决策单调性，把单调栈改成双端队列，每次不断从队首弹出不够优的决策点。
时间复杂度\(O(nk)\)。
为什么uoj上的样例本机AC提交RE？？？删掉inline还T？？？卡常数！手动把函数压倒主函数里，快速读入，还有二维数组把较小的一维放在前面，这个优化效果最明显！
#include
#include
#include
using namespace std;
typedef long long ll;
int in() {
char c = getchar();
int k = 0;
for (;
c < '0' || c > '9';
c = getchar());
for (;
c >= '0' && c <= '9';
c = getchar())
k = k * 10 + (c ^ 48);
return k;
}const int N = 100003;
const int K = 203;
int n, k, pre[K][N], a[N], head, tail, qu[N];
ll f[K][N], S, sum[N], qucal[N];
ll calzj;
int cut[N], cuttot = 0;
int main() {
n = in();
k = in();
for (int i = 1;
i <= n;
++i) sum[i] = sum[i - 1] + (a[i] = in());
S = sum[n];
for (int i = 1;
i <= n;
++i)
f[1][i] = 1ll * sum[i] * (S - sum[i]);
for (int j = 2;
j <= k + 1;
++j) {
head = 0;
tail = 0;
qu[0] = 0;
for (int i = 1;
i <= n;
++i) {
while (head < tail && qucal[head + 1] - qucal[head] >= (sum[qu[head + 1]] - sum[qu[head]]) * (sum[i] * -2)) ++head;
ll sumlr = sum[i] - sum[qu[head]];
f[j][i] = f[j - 1][qu[head]] + sumlr * (S - sumlr);
pre[j][i] = qu[head];
calzj = f[j - 1][i] - S * sum[i] - sum[i] * sum[i];
while (head < tail && (sum[qu[tail]] == sum[i] ? (calzj >= qucal[tail]) : (calzj - qucal[tail]) * (sum[qu[tail]] - sum[qu[tail - 1]]) > (qucal[tail] - qucal[tail - 1]) * (sum[i] - sum[qu[tail]]))) --tail;
if (sum[qu[tail]] != sum[i]) qu[++tail] = i, qucal[tail] = calzj;
else if (head == tail && calzj >= qucal[head]) qu[tail] = i, qucal[tail] = calzj;
}
}printf("%lld\n", f[k + 1][n] >> 1);
int tmp = n;
for (int i = k + 1;
i > 1;
--i)
tmp = cut[++cuttot] = pre[i][tmp];
for (int i = cuttot;
i >= 1;
--i) printf("%d ", cut[i]);
return 0;
}
转载于:https://www.cnblogs.com/abclzr/p/6723784.html
推荐阅读
