题目传送门(BZOJ)
>原文链接<

题解 :

状态 :

F[i]表示处理完第i句话的最小不协调度

暴力转移 :

F[i] = \min{F[j]+(s[i]-s[j]-L)^p}

p = 2时, 这部分数据应该是给斜率优化的分

我们发现这样的一个性质(四边形不等式) :

j_1 < j_2 < i_1时, 若从j_2转移至i_1比从j_1转移至i_1优,

那么对于i_2一定有同样的结果, 化成式子就是这个意思 :

\because F[j_1]+calc(j_1, i_1) \ge F[j_2]+calc(j_2, i_1)

j_1 < j_2 < i_1

\therefore F[j_1]+calc(j_1, i_2) \ge F[j_2]+calc(j_2, i_1)

对于本题, 可以利用反证法证明满足四边形不等式

决策单调性 :

由于满足四边形不等式, 使用决策单调性解决本题.

下面引用了Winniechen对决策单调性的讲解 :

假如现在,队列中为空,也就是没有一个状态被确定,那么,所有点的最优转移都从0转移,也就是

0,0,0,0,0,0,0

现在,我们用0更新了1这个点,因为DP方程具有决策单调性,那么假如x点用1转移比用0转移更优,那么x到n的所有点都满足由1转移到0更优,而这个最小的x通过二分查找找到,将1压入队列。

0,0,1,1,1,1,1

假设,现在到达这个转移状态,我们继续用0更新了2,现在2进入了决策选择中,假如用2更新3不如用1更新,那么2的x点必定在5之后,也就是x后的某个通过二分查找找到的点,将2压入队列。

0,0,1,1,1,2,2

假设,现在到达这个转移状态,我们用1更新3,现在3进入的决策选择中,假如用3更新6比用2更新6更优,那么2就可以弹出队列,因为不存在一个点用2转移最优,之后再在1上二分查找x,之后更新状态。

按如上规则更新答案, 即可解决本题.

代码 :

#include <cstdio>#include <cstring>#define ll long double#define ff(x, y) (f[x]+qp(s[y]-s[x]-L, p))const int N = 101010;struct Node { int l, r, p; Node(){} Node(int __l, int __r, int __p) {l = __l, r = __r, p = __p;}}q[N];char str[N][35];ll f[N], s[N];int fr[N], T, n, L, p;inline ll qp(ll x, int y) { x = x > 0 ? x : -x; ll ret = 1; for(;y;y>>=1, x=x*x) {if(y&1) ret=ret*x;} return ret;}inline int find(const Node &a, int x) { int l = a.l, r = a.r + 1; while(l < r) { int mid = (l+r) >> 1; if(ff(x, mid) > ff(a.p, mid)) l = mid+1; else r = mid; } return l;}void print(int cur) { if(!cur) return ; print(fr[cur]); for(int i = fr[cur]+1; i < cur; i ++ ) printf("%s ", str[i]); puts((const char*)str[cur]);}int main() { scanf("%d", &T); while(T -- ) { scanf("%d%d%d", &n, &L, &p); L ++; *s = *f = 0; for(int i = 1; i <= n; i ++ ) scanf("%s", str[i]), s[i] = s[i-1]+strlen(str[i])+1; int l = 0, r = 0; q[r++] = Node(1, n, 0); for(int i = 1; i <= n; i ++ ) { if(q[l].r < i && l < r) l ++ ; f[i] = ff(q[l].p, i); fr[i] = q[l].p; if(ff(i, n) <= ff(q[r-1].p, n)) { while(l < r && ff(i, q[r-1].l) <= ff(q[r-1].p, q[r-1].l)) r --; if(l == r) q[r++] = Node(i+1, n, i); else { int cur = find(q[r-1], i); q[r-1].r = cur - 1; q[r++] = Node(cur, n, i); } } } if(f[n] > 1e18) puts("Too hard to arrange"); else printf("%.0Lf\n", f[n]); puts("--------------------"); }}