【BZOJ】3675:[Appio 2014]シーケンス分割

http://www.lydsy.com/JudgeOnline/problem.php?id=3675
1つのn個の数字のシーケンスには、各分割の寄与は$sum(left,mid)*sum(mid+1,right)$であり、ここでleft$は本シーケンスの一番左を表しています.シーケンスを分割するたびに半分になります.k回分割して得た最大貢献と.n<=100000,k<=200

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100005;

ll s[N], d[2][N];

int n, K, q[N], fr, ta;

int main() {

	scanf("%d%d", &n, &K);

	for(int i=1; i<=n; ++i) scanf("%lld", &s[i]), s[i]+=s[i-1];

	ll *now=d[0], *last=d[1];

	for(int p=1; p<=K; ++p) {

		fr=ta=0; q[ta++]=0;

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

			while(fr!=ta-1 && last[q[fr]]-last[q[fr+1]]<=(s[q[fr]]-s[q[fr+1]])*(s[n]-s[i])) fr++;

			int j=q[fr];

			now[i]=last[j]+(s[i]-s[j])*(s[n]-s[i]);

			while(fr!=ta-1 && (last[i]-last[q[ta-2]])*(s[q[ta-1]]-s[q[ta-2]])>=(last[q[ta-1]]-last[q[ta-2]])*(s[i]-s[q[ta-2]])) --ta;

			q[ta++]=i;

		}

		swap(last, now);

	}

	ll ans=0;

	for(int i=1; i<=n; ++i) ans=max(ans, last[i]);

	printf("%lld
", ans);

	return 0;

}

　　
laekovから特殊な性質を分析すると聞いて分析しました.各ブロックの答えへの貢献は$sum(このブロック)*sum(残りの要素)$であり、最後はもちろん2で割ることができます.でも、適当にやってもいいです...
dpを考慮して、$d(i,j)$を設定して、このシーケンスは$iで$jを分割して得られた答えを表し、$jは$iで分割されます.
入手しやすい:
$d(i,j)=max(d(k,j-1)+sum(k+1,i)*sum(i+1,n)$
得られたブロックは$(k＋1、i)であり、これらの値に対する積を先に計算したので、もう一度計算しなくてもいいです.
それから$s(n)=\sum_｛i=1｝^{n}a[i]$では
$d(i,j)=max(d(k,j-1)+(s(i)-s(k)*(s(n)-s(i)))$
そして傾きを最適化すればいいです.
(久しぶりに書いて、凸殻を維持している時に、全体の人がsbになったことに気づきました...チームの最後は凸殻を維持しないで、4発のwaを渡したのに、見つけられませんでした.