[bzoj1563][DP]诗人小G

Description

Input

Output

对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出”Too hard to
arrange”(不包含引号)。每个输出后面加”——————–”

Sample Input

4

4 9 3

brysj,

hhrhl.

yqqlm,

gsycl.

4 9 2

brysj,

hhrhl.

yqqlm,

gsycl.

1 1005 6

poet

1 1004 6

poet

Sample Output

108

---

32

---

Too hard to arrange

---

1000000000000000000

---

HINT

总共10个测试点，数据范围满足：

测试点 T N L P 1 ≤10 ≤18 ≤100 ≤5 2 ≤10 ≤2000 ≤60000 ≤10
3 ≤10 ≤2000 ≤60000 ≤10 4 ≤5 ≤100000 ≤200 ≤10 5 ≤5 ≤100000 ≤200 ≤10
6 ≤5 ≤100000 ≤3000000 2 7 ≤5 ≤100000 ≤3000000 2
8 ≤5 ≤100000 ≤3000000 ≤10 9 ≤5 ≤100000 ≤3000000 ≤10
10 ≤5 ≤100000 ≤3000000 ≤10 所有测试点中均满足句子长度不超过30。

【样例说明】

前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。

题解

四边形不等式优化一维dp的应用
很明显有转移方程

$$f[i]=min(f[j]+val(j,i))$$
其中 $val(j,i)=|sum[i]-sum[j]+(i-j-1)-L|^p$
其中 $sum[i]$表示前i首诗的长度和
我们只需要证明 $val(j,i)$函数满足四边形不等式即可
只需证明
$$val(j,i)+val(j+1,i+1)<=val(j,i+1)+val(j+1,i)$$
移项有
$$val(j,i)-val(j,i+1)<=val(j+1,i)-val(j+1,i+1)$$
记 $u=(sum[i]+i)-(sum[j]+j)-(L+1)$
记 $v=(sum[i]+i)-(sum[j+1]+j+1)-(L+1)$
即证明
$$|u|^p-|u+a[i+1]+1|^p<=|v|^p-|v+a[i+1]+1|^p$$
显然有 $u>v$，即证明函数 $y=|x|^p-|x+c|^p$在常数c任意取值的情况下均有单调递减性
设p为奇数， $x=[-c,0]$时，函数写作 $y=-x^p-(x+c)^p$
对y求导
可得导函数 $y'=-p*x^{p-1}-p*(x+c)^{p-1}$
因为p-1是偶数，p是正整数
所以导函数 $y'$恒小于0
所以在该段下恒有函数y单调递减
对于p和c满足其他情况时也可运用导函数的知识证明函数y单调递减
如此可知道函数 $val(j,i)$满足四边形不等式
于是f数组满足决策单调性
我们就可以愉快的 $nlogn$解决啦

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define LL long double
#define mx 1000000000000000000LL
using namespace std;
inline LL read()
{LL x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
LL pow_mod(LL a,int b)
{LL ret=1;while(b){if(b&1)ret=ret*a;a=a*a;b>>=1;}return ret;
}
int n;
LL L,p;
LL f[100005],sum[100005];
LL S(int px,int py){
   return f[py]+pow_mod(abs(sum[px]-sum[py]+px-py-1-L),p);}//i,j
struct node{
   int c,l,r;}li[100005];int h,t;
char ch[35];
int main()
{int T;scanf("%d",&T);while(T--){n=read();L=read();p=read();for(int i=1;i<=n;i++){scanf("%s",ch+1);int len=strlen(ch+1);sum[i]=sum[i-1]+len;}li[1].c=0;li[1].l=0;li[1].r=n;h=t=1;for(int i=1;i<=n;i++){if(li[h].r==i-1)h++;li[h].l=i;f[i]=S(i,li[h].c);if(h>t || S(n,i)<=S(n,li[t].c)){while(h<=t && S(li[t].l,i)<=S(li[t].l,li[t].c))t--;if(h>t){li[++t].l=1;li[t].r=n;li[t].c=i;}else{int l=li[t].l,r=li[t].r;while(l<=r){int mid=(l+r)>>1;if(S(mid,i)<=S(mid,li[t].c))r=mid-1;else l=mid+1;}li[t].r=l-1;li[++t].l=l;li[t].r=n;li[t].c=i;}}}if(f[n]>mx)printf("Too hard to arrange\n");else printf("%lld\n",(long long)f[n]);printf("--------------------\n");}return 0;
}