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。

 

题解如下

https://www.byvoid.com/blog/noi-2009-poet

我只放AC代码

1 #include
      
        2 #include
       
         3 #define ll long double  4 struct node{
    int  l,r,p;}q[100100]; 5 #define MAX 1000000000000000000LL  6 #define N 100100 7 ll sum[N],f[N]; 8 int n,l,p,T; 9 char ch[35];10 ll pow(ll y){11     if(y<0)y=-y;12     ll ans=1;13     for (int i=1;i<=p;i++) ans*=y;14     return ans;15 }16 17 ll calc(int x,int y){18     return f[x]+pow(sum[y]-sum[x]+(y-x-1)-l);19 }20 21 int find(node t,int x){22     int l=t.l,r=t.r;23     while(l<=r){24         int mid=(l+r)>>1;25         if (calc(x,mid)<=calc(t.p,mid)) r=mid-1;26         else l=mid+1;27     }28     return l;29 }30 31 void dp(){32     int head=1,tail=0;33     q[++tail]=(node){
    0,n,0};34     for (int i=1;i<=n;i++){35         if(q[head].r
        
         <=tail) head++;36         f[i]=calc(q[head].p,i);37         if (head>tail||calc(i,n)<=calc(q[tail].p,n)){38             while(head<=tail&&calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l)) tail--;39             if(head>tail)q[++tail]=(node){i,n,i};40             else{41                 int x=find(q[tail],i);42                 q[tail].r=x-1;43                 q[++tail]=(node){x,n,i};44             }45         }46     }47 }48 49 int main(){50     scanf("%d",&T);51     while(T--){52         scanf("%d%d%d",&n,&l,&p);53         for (int i=1;i<=n;i++) scanf("%s",ch),sum[i]=sum[i-1]+strlen(ch);54         dp();55         if(f[n]>MAX)56             puts("Too hard to arrange");57         else 58             printf("%lld\n",(long long)f[n]);59         puts("--------------------");60     }61 }