【BZOJ 1563】 [NOI2009]诗人小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
——————–

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

HINT

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

测试点TNLP
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≤30000002
7≤5≤100000≤30000002
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代码

 #include<cstdio>
 #include<cstring>
 #define ll long double
 struct node{int  l,r,p;}q[];
 #define MAX 1000000000000000000LL
 #define N 100100
 ll sum[N],f[N];
 int n,l,p,T;
 char ch[];
 ll pow(ll y){
     if(y<)y=-y;
     ll ans=;
     for (int i=;i<=p;i++) ans*=y;
     return ans;
 } ll calc(int x,int y){
     return f[x]+pow(sum[y]-sum[x]+(y-x-)-l);
 } int find(node t,int x){
     int l=t.l,r=t.r;
     while(l<=r){
         int mid=(l+r)>>;
         if (calc(x,mid)<=calc(t.p,mid)) r=mid-;
         else l=mid+;
     }
     return l;
 } void dp(){
     int head=,tail=;
     q[++tail]=(node){,n,};
     for (int i=;i<=n;i++){
         if(q[head].r<i&&head<=tail) head++;
         f[i]=calc(q[head].p,i);
         if (head>tail||calc(i,n)<=calc(q[tail].p,n)){
             while(head<=tail&&calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l)) tail--;
             if(head>tail)q[++tail]=(node){i,n,i};
             else{
                 int x=find(q[tail],i);
                 q[tail].r=x-;
                 q[++tail]=(node){x,n,i};
             }
         }
     }
 } int main(){
     scanf("%d",&T);
     while(T--){
         scanf("%d%d%d",&n,&l,&p);
         for (int i=;i<=n;i++) scanf("%s",ch),sum[i]=sum[i-]+strlen(ch);
         dp();
         if(f[n]>MAX)
             puts("Too hard to arrange");
         else
             printf("%lld\n",(long long)f[n]);
         puts("--------------------");
     }
 }