BZOJ 1563 「NOI2009」诗人小 G

神仙 DP……

朴素转移：fi=min0≤j<i(fj+|sumi−sumj+i−j−1−L|P)。
其中 sumi 表示前 i 个句子的长度之和，注意要算上空格。
下文中用 si 表示第 i 个句子的长度。

考虑优化这个式子。
首先要知道决策单调性，即每一个状态的最优决策需要有单调性，一般来说都是单调不降。
这样的话，可以考虑转移完 i 时，考虑 i 目前可以作为哪些未来状态的最优决策。

类似珂朵莉树，维护若干个三元组 (d,l,r)，表示 d 目前是 ∀i∈[l,r]，fi 的最优决策。
出现新的 i 时，即可在已有的三元组中排除掉比这个差的，最后会找到一个三元组使得 [l,r] 中有一部分优于这个，有一部分劣于这个。
但是因为有决策单调性，所以直接二分找到这个分界点，然后更新。

然后考虑怎么维护这些三元组。
其实是可以直接线段树区间赋值维护决策的，二分也挺方便。
不过可以用单调队列减少常数。

然鹅知道这个有什么用吗……
我们怎么知道它有决策单调性？
（暴力找规律）

于是引入一个东西：四边形不等式。
这个东西通常的定义是：若 w(x,y) 是一个二元函数，对于任意 a<b<c<d，都有 w(a,d)+w(b,c)≥w(a,c)+w(b,d)，则称 w 满足四边形不等式。
然后有另一个定义：对于 a<b，都有 w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)。
这两个互为充要条件，这里就不证了。

接下来有一个定理，如果某 DP 方程长这样：fi=min0≤j<i(fj+w(j,i))。
那么当 w 满足四边形不等式时，f 有决策单调性。

证明：
∀1≤i<k≤n,1≤j<di，其中 di 表示 fi 的最优决策。
有 fdi+w(di,i)≤fj+w(j,i)

根据四边形不等式的定义有 w(j,k)+w(di,i)≥w(j,i)+w(di,k)

移项得 w(di,k)−w(di,i)≤w(j,k)−w(j,i)

与前面那个式子相加，得 fdi+w(di,k)≤fj+w(j,k)

于是得 j<dk，证毕。

那么这题的 w(x,y) 即 |sumy−sumx+y−x−1−L|P。
我们尝试证明其满足四边形不等式。
即证明 ∀a<b,w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)。

设 x=sumb−suma+b−a−1−L，
原式即 |x|P+|x+sb+1−sa+1|P≤|x+sb+1+1|P+|x−sa+1−1|P

移项，设 y=sumb+1−suma+b−a−L，有 |x|P−|x−sa+1−1|P≤|y|P−|y−sa+1−1|P

显然 x<y，
问题变成证明对于常正整数 c,P，y=|x|P−|x−c|P 单调不下降。

考虑对其求导，若 y′≥0 则该命题得证。
分类讨论，首先考虑 P 为偶数的情况，这种情况显然比较简单，因为可以直接把绝对值去掉。
y′=(xP−(x−c)P)′=PxP−1−P(x−c)P−1≥0

考虑 P 为奇数的情况，这时就得分别讨论这两项的正负性。
考虑只有前一项为非负数，即 0≤x 但 x−c<0。
有 y′=(xP+(x−c)P)′=PxP−1+P(x−c)P−1

在题目中用到的 c 可以保证 x+(x−c)≥0，所以显然这个也 ≥0。

考虑两项都为负数，即 x<0 的情况。
有 y′=(−xP+(x−c)P)′=−PxP−1+P(x−c)P−1

根据 x−c<x 有 −(x−c)>x，所以这个也 ≥0。

证毕。

于是用一开头提到的方法做就可以了。
注意 long long 依然不够，要 long double。
把代码中的注释去掉就可以在洛谷上通过了，这是 BZOJ AC 代码。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5;
const int LEN = 30;
int T,n,l,p;
inline long double fpow(long double a,int b)
{
    long double ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = ret * a),a = a * a;
    return ret;
}
long double f[N + 5];
struct note
{
    int x,l,r;
} q[N + 5];
int head,tail,d[N + 5];
long double sum[N + 5];
char s[N + 5][LEN + 5];
inline long double calc(int x,int y)
{
    return f[x] + fpow(fabsl(sum[y] - sum[x] + y - x - 1 - l),p);
}
int main()
{
    scanf("%d",&T);
    for(;T--;puts("--------------------"))
    {
        scanf("%d%d%d",&n,&l,&p);
        for(register int i = 1;i <= n;++i)
            scanf("%s",s[i]),sum[i] = sum[i - 1] + strlen(s[i]);
        q[head = tail = 1] = (note){0,1,n};
        for(register int i = 1;i <= n;++i)
        {
            for(;head < tail && q[head].r < i;++head);
            f[i] = calc(q[head].x,i),d[i] = q[head].x;
            if(calc(q[tail].x,q[tail].r) > calc(i,q[tail].r))
            {
                for(;head < tail && calc(q[tail].x,q[tail].l) >= calc(i,q[tail].l);--tail);
                int now,l = q[tail].l,r = n,mid;
                while(l <= r)
                {
                    mid = l + r >> 1;
                    if(calc(q[tail].x,mid) >= calc(i,mid))
                        r = mid - 1,now = mid;
                    else
                        l = mid + 1;    
                }
                q[tail].r = now - 1,q[++tail] = (note){i,now,n};
            }
        }
        if(f[n] <= 1e18)
        {
            printf("%.0Lf\n",f[n]);
            /*tail = 0;
            for(register int i = n;i;i = d[i])
                q[++tail] = (note){0,d[i] + 1,i};
            for(;tail;--tail)
                for(register int i = q[tail].l;i <= q[tail].r;++i)
                    printf("%s%c",s[i]," \n"[i == q[tail].r]);*/
        }
        else
            puts("Too hard to arrange");
    }
}