BZOJ1563:[NOI2009]诗人小G(决策单调性DP)

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。

Solution

题解

自闭了

Code

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #define N (100009)

 #define LL long double

 #define MAX 1e18

 using namespace std;

 struct Node{int l,r,p;}q[N];

 int T,n,l,p;

 LL sum[N],f[N];

 char s[N][];

 LL Calc(int j,int i)

 {

     return f[j]+pow(abs(sum[i]-sum[j]+i-j--l),p);

 }

 int Find(Node t,int x)

 {

     int l=t.l,r=t.r,ans=t.r+;

     while (l<=r)

     {

         int mid=(l+r)>>;

         if (Calc(x,mid)<=Calc(t.p,mid))

             ans=mid,r=mid-;

         else l=mid+;

     }

     return ans;

 }

 void DP()

 {

     int head=,tail=;

     q[]=(Node){,n,};

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

     {

         if (head<=tail && i>q[head].r) head++;

         f[i]=Calc(q[head].p,i);

         if (head>tail || Calc(i,n)<=Calc(q[tail].p,n))

         {

             while (head<=tail && Calc(i,q[tail].l)<=Calc(q[tail].p,q[tail].l)) tail--;

             if (head>tail) q[++tail]=(Node){i,n,i};

             else

             {

                 int now=Find(q[tail],i);

                 q[tail].r=now-;

                 q[++tail]=(Node){now,n,i};

             }

         }

     }

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d%d%d",&n,&l,&p);

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

             scanf("%s",s[i]);

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

             sum[i]=sum[i-]+strlen(s[i]);

         DP();

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

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

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

     }

 }