第一次写这种二分来优化决策单调性的问题。。。。 调了好久，，，各种细节问题
显然有DP方程：
$f[i]=min(f[j] + qpow(abs(sum[i] - sum[j] - L - 1)));$
其中f[i]代表到了第i个句子的最小答案
qpow用于处理^p
sum为前缀和
（同时为了处理句子之间的空格问题，我们在统计前缀和的时候就默认在句子后面加一个空格，
然后在计算的时候，由于每一行只有最后一个不用加空格，直接减掉这个多加的空格即可获得正确长度）
首先我们可以打表发现是满足决策单调性的，
即决策是一段一段的
比如这种:
11122224446666
但下面这两种则不满足决策单调性:
11144442222666
11112424
同时这样的决策单调性是很特殊的，即一开始可能是这样的
11111111111111
加入2后：
11122222222222
加入4后：
11122224444444
也就是说就算最终取值是11122224446666，
在中间不断插入的过程中，也是一整段的
因此满足可二分性，
所以我们可以二分来找每个决策管理的区间（即可以转移到的区间）
但是有如下细节需要注意：
1，区间可能被完整覆盖
举个栗子，
如果当前状态是
111111111111114
现在加入一个5，那么下一个状态完全有可能是:
111111155555555
因此为了处理这样的情况，我们在二分之前先将会被完整覆盖的区间pop掉
即在插入5前弹出4，
同时这里又要注意，这个pop的处理必须在二分之前，
因为在二分过程中，我们需要一个决策来起到check的作用，而这个决策应该是当前插入的x最后应该被放入的那个区间的决策。
这样说可能不太清楚，还是举个栗子
比如当前状态：
111111112222223333
假设下一个状态是
111111112224444444
那么我们二分过程中作为判断依据的那决策就应该是2，
why？
因为观察到3号决策已经被完整的覆盖了，那么我们要对3之前的状态进行check的时候，由于3号不够优（也有可能是受到只能向后转移的限制），我们不能使用3号来check，
但是直接使用2号决策来check，然后在后面2222223333中二分也是不妥的，
因为在3333时，2号并不是最优，
所以为了应对这种情况，
我们先直接判断3333中的第一个3所对应的DP状态，如果插入的x更加优，
那么就代表这个区间是可以被完整的覆盖的，因此我们pop掉这个区间，
依次pop直到不满足条件为止，
这个时候我们就只需要在222222中二分了，于是用2号决策来check就很顺理成章了
2，新插入的x可能什么区间都覆盖不了，
也就是说新插入的x可能并不能更新状态，于是我们在二分前做一次特判，
判断当前区间的最后一个是否可以被覆盖,
如果不能，那么这个x无法更新状态，
所以直接continue
---------------以上为计算答案过程--------------
----------------以下为输出部分----------------
因为要输出方案，因此我们在转移时用last数组来记录i是从哪个决策转移而来
又因为不能打乱顺序，所以我们用Next数组来反向记录last数组
比如last中记录的可能是
0 <--- 2 <--- 4
即4由2转移而来，2由转移0而来
那么我们Next数组中记录的就是
0 ---> 2 ---> 4
所以我们从1开始输出，
每当我们到达Next[now]时就输出换行
即输出
1 2
3 4
其实也就是相当于存下了每一行是由哪一句话结尾的，
然后依次输出
最后注意ans可能很大，而且要与1e18比较，所以long long 不够用。
要用 long double
下面是代码（中间有调试输出）
其实感觉比斜率优化好理解多了。。。。。QAQ难道是我太蠢了么
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 100100 5 #define LL long long 6 #define LD long double 7 #define ACway 101000 8 #define inf 1000000000000000000LL 9 int t,L,p,n; 10 int s[AC],last[AC],l[AC],r[AC];//对应决策的管理区间 11 int q[AC],head,tail;//存下当前是哪个决策 12 int Next[AC];//对last进行相反操作,以便输出 13 LD f[AC]; 14 LL sum[AC]; 15 char ss[ACway][45]; 16 //bool flag; 17 /*为什么我感觉就是一个普通DP+决策单调性 ---> 二分,,,,这个不比斜率优化容易理解么？*/ 18 inline LD qpow(LD x)//error!!!x也要用LD！！！ 19 { 20 LD ans=1; 21 // printf("x : %lld ",(LL)(x + 0.5)); 22 int have=p; 23 while(have) 24 { 25 if(have & 1) ans*=x; 26 x*=x; 27 have>>=1; 28 // if(ans > inf || x > inf) flag=true; 29 } 30 // printf("ans : %lld ",(LL)(ans + 0.5)); 31 return ans; 32 } 33 34 inline void pre() 35 { 36 scanf("%d%d%d",&n,&L,&p); 37 for(R i=1;i<=n;i++) 38 { 39 scanf("%s",ss[i]+1); 40 s[i]=strlen(ss[i]+1) + 1;//加上后面的空格 41 sum[i]=sum[i-1] + s[i];//求出前缀和 42 } 43 } 44 45 inline LD count(int x,int j)//j --- > x 46 { 47 return f[j] + qpow(abs(sum[x] - sum[j] - L - 1)); 48 } 49 50 void half(int x)//二分查找 51 { 52 int now=q[tail],ll=l[now],rr=n,mid;//因为可能可以覆盖多个区间 53 while(ll < rr) 54 { 55 mid=(ll + rr) >> 1; 56 if(count(mid,x) < count(mid,now)) rr=mid;//如果更优就往左缩短 57 else ll=mid + 1;//不然就向右寻找 58 } 59 // while(l[q[tail]] >= ll) --tail;//去掉整个都被包含的区间 60 r[q[tail]]=ll-1; 61 q[++tail]=x,l[x]=ll,r[x]=n; 62 /*for(R i=head;i<=tail;i++) 63 { 64 for(R j=l[q[i]];j<=r[q[i]];j++) 65 printf("%d",q[i]); 66 } 67 cout << endl;*/ 68 } 69 70 inline void getans() 71 { 72 head=1,tail=1; 73 q[1]=0,l[0]=1,r[0]=n; 74 for(R i=1;i<=n;i++) 75 { 76 while(r[q[head]] < i) ++head;//如果当前队首已经取不到了 77 int now=q[head]; 78 //f[i]=f[now] + qpow(abs(sum[i] - sum[now] - L - 1)); 79 f[i]=count(i,now);//error ??? 用函数的话会爆了会自动转换为inf? 80 //error!!!是后者转移到前者，所以是now ---> i,要填count(i,now),而不是count(now,i); 81 // printf("???%d ",now); 82 last[i]=now; 83 if(count(n,q[tail]) < count(n,i)) continue;//如果最后一个都不够优，那就不二分了 84 while(count(l[q[tail]],q[tail]) > count(l[q[tail]],i)) --tail;//如果当前可以覆盖前面的整个区间 85 half(i);//注意上面的while要在调用half之前修改，这样取到的now才是正确的 86 } 87 } 88 89 inline void write() 90 { 91 //if(f[n] > inf || flag) puts("Too hard to arrange"); 92 if(f[n] > inf) puts("Too hard to arrange"); 93 else 94 { 95 printf("%lld ",(LL)(f[n] + 0.5));//注意精度误差 96 for(R i=n ; i ; i=last[i]) Next[last[i]]=i; 97 int now=0; 98 for(R i=1;i<=n;i++) 99 { 100 now=Next[now];//now先跳了吧 101 int be=now;//先只到这行结尾，因为for还要加的 102 for(R j=i; j < be ;j++) printf("%s ",ss[j] + 1); 103 printf("%s ",ss[be] + 1); 104 i=be;//最后再赋i,因为for中还要用到当前i 105 } 106 } 107 puts("--------------------"); 108 } 109 110 inline void check() 111 { 112 for(R i=1;i<=n;i++) 113 { 114 if(r[i] > l[i]) 115 for(R j=l[i];j<=r[i];j++) printf("%d",i); 116 } 117 printf(" "); 118 for(R i=1;i<=n;i++) printf("!!!%lld ",(LL)(f[i] + 0.5)); 119 cout << endl << endl; 120 } 121 122 inline void work() 123 { 124 while(t--) 125 { 126 //flag=false; 127 pre(); 128 getans(); 129 // check(); 130 write(); 131 } 132 } 133 134 int main() 135 { 136 freopen("in.in","r",stdin); 137 scanf("%d",&t); 138 work(); 139 fclose(stdin); 140 return 0; 141 }