这个题一看数字就很爆炸啊。。不过先不管他。。
先对长度+1，然后取个前缀和设为a
设d[i]为取到i个句子且当前行以i句结尾的最小代价
d[i]=max{d[j]+|a[i]-a[j]-L-1|^p}
显然f(x)=|x|^p是个下凸函数，即x越大导数越大。。
然后考虑2个决策点j<k<i
如果d[j]+|a[i]-a[j]-L-1|^p>d[k]+|a[i]-a[k]-L-1|^p，那么此后j就不会比k更优了。。
所以用单调队列存递增的决策点，用上面的式子去队尾就可以了。。
然而数非常爆炸，在比较的时候很麻烦，于是用long double(double都不行= =)来做大数比较，虽然有精度误差但是问题不大。。
复杂度O(Tnlognlogp)，常数巨大。。
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 100005
#define nm 200005
#define pi 3.1415926535897931
using namespace std;
const ll inf=1e18;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,L,p,qh,qt,q[NM],f[NM],v[NM],a[NM];
char _s[50];
long double d[NM];
long double qpow(long double x,int t){return t?qpow(sqr(x),t>>1)*(t&1?x:1):1;}
int main(){
freopen("data.in","r",stdin);
int _=read();while(_--){
mem(d);mem(f);mem(v);
n=read();L=1+read();p=read();
inc(i,1,n){scanf("%s",_s);a[i]=a[i-1]+1+strlen(_s);}
q[qh=qt=1]=0;
inc(i,1,n){
f[i]=max(f[i],f[i-1]);
while(qh<=qt&&f[i]!=q[qh])qh++;
d[i]=d[q[qh]]+qpow(abs(a[i]-a[q[qh]]-L),p);
int s=i+1;
while(qh<=qt){
s=n+1;
#define fun(t) d[t]+qpow(abs(a[mid]-a[t]-L),p)
for(int x=i+1,y=n;x<=y;)
if(fun(q[qt])>fun(i))s=mid,y=mid-1;else x=mid+1;
if(s<=v[q[qt]])qt--;else break;
}
if(s<=n)f[s]=i,v[i]=s,q[++qt]=i;
}
//inc(i,1,n)printf("%d ",a[i]-a[i-1]);putchar('\n');
//inc(i,1,n)printf("%d ",f[i]);putchar('\n');
//inc(i,1,n)printf("%lld ",d[i]);putchar('\n');
if(d[n]>inf)printf("Too hard to arrange\n");else printf("%lld\n",(ll)d[n]);
printf("--------------------\n");
}
return 0;
}
1563: [NOI2009]诗人小G
Time Limit: 100 Sec Memory Limit: 64 MB
Submit: 3017 Solved: 1017
[Submit][Status][Discuss]
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
--------------------
【样例说明】
前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。
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。
Source
[Submit][Status][Discuss]