bzoj1563: [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个测试点，数据范围满足：

测试点 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

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 typedef long double int64;

 const int maxn=;

 const int maxl=;

 const int64 maxval=1E18;

 char s[maxl];

 int T,n,l,p;

 int64 sum[maxn],f[maxn];

 bool flag;

 int64 ksm(int64 a,int b){

     int64 t;

     for (t=;b;a*=a,b>>=) if (b&) t*=a;

     return t;

 }

 int64 calc(int j,int i){return f[j]+ksm(abs(sum[i]-sum[j]+i-j--l),p);}

 struct Stack{

     int top,pos;

     struct Data{

         int st,ed,id;

     }s[maxn],tmp;

     void init(){s[top=]=(Data){,n,},pos=;}

     bool cmp(int t,int x,int y){return calc(x,t)<calc(y,t);}

     int get(int id){

         int l=tmp.st,r=tmp.ed,m,a=tmp.id;

         while (l<r){

             m=((l+r)>>)+;

             if (cmp(m,a,id)) l=m; else r=m-;

         }

         return l;

     }

     void push(int id){

         while (top&&!cmp(s[top].st,s[top].id,id)) top--;

         tmp=s[top--];

         int m=get(id);

         if (tmp.st<=m) s[++top]=(Data){tmp.st,m,tmp.id};

         if (m<n) s[++top]=(Data){m+,n,id};

     }

     int64 query(int x){

         while (x>s[pos].ed) pos++;

         return calc(s[pos].id,x);

     }

 }stack;

 int main(){

     for (read(T);T;T--){

         read(n),read(l),read(p);

         for (int i=;i<=n;i++) scanf("%s",s+),sum[i]=sum[i-]+strlen(s+);

         stack.init(),flag=;

         for (int i=;i<=n;i++){

             f[i]=stack.query(i);

             stack.push(i);

         }

         if (f[n]>maxval) puts("Too hard to arrange");

         else printf("%lld\n",(long long)f[n]);

         puts("--------------------");

     }

     return ;

 }

秒客网