1563: [NOI2009]诗人小G

https://lydsy.com/JudgeOnline/problem.php?id=1563

分析：

　　直接转移f[i]=f[j]+cost(i,j)，cost(i,j)=(sum[i]-sum[j])

　　然后有决策单调性，就可以二分+队列了。注意两个字符串之间还有一个空格，所以长度+1，很多字符串合起来后，总的长度还要-1，最后一个没空格。

　　证明？byvoid

　　luogu输出方案，加上后一直过不了，g,nxt数组是输出方案的部分

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 typedef long double LD;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

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

 }

 const int N = ;

 const LL INF = 1e18;

 char str[N][], pr[];

 int len[N], g[N], nxt[N];

 LD f[N];

 LL sum[N];

 int n, Len, P;

 struct Node{

     int p, l, r;

     Node() {}

     Node(int _,int __,int ___) { p = _, l = __, r = ___; }

 }q[N];

 LD ksm(LD x) {

     LD ans = ; int b = P;

     while (b) {

         if (b & ) ans = ans * x;

         x = x * x;

         b >>= ;

     }

     return ans;

 }

 void init() {

     n = read(), Len = read(), P = read();

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

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

         sum[i] = sum[i - ] + (len[i] = strlen(str[i] + ) + );

     }

 }

 LD Calc(int i,int j) {

     return f[j] + ksm(abs(sum[i] - sum[j] - Len - ));

 }

 int binary_search(int l,int r,int x,int y) {

     int ans = n;

     while (l <= r) {

         int mid = (l + r) >> ;

         if (Calc(mid, x) < Calc(mid, y)) ans = mid, r = mid - ;

         else l = mid + ;

     }

     return ans;

 }

 void solve() {

     int L = , R = ;

     q[++R] = Node(, , n);

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

         while (L <= R && q[L].r < i) L ++;

         int j = q[L].p;

         f[i] = Calc(i, j);

         g[i] = j;

         if (Calc(n, q[R].p) < Calc(n, i)) continue; // 如果最后一个点从i转移不优，那么说明i没有覆盖的区间，不需要二分了

         while (L <= R && Calc(q[R].l, q[R].p) > Calc(q[R].l, i)) R --;

         q[R].r = binary_search(q[R].l, n, i, q[R].p) - ;

         q[++R] = Node(i, q[R - ].r + , n);

     }

 }

 void print() {

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

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

     puts(pr);

 }

 int main() {

     strcpy(pr, "--------------------");

     int T = read();

     while (T--) {

         init();

         solve();

         print();

     }

     return ;

 }