P<=10一开始是吓死我了

后来想到这就是一个经典的决策单调性解决1d1d动态规划的题目

像决策单调性完全可以打表找规律，这里有一篇严谨的证明https://www.byvoid.com/blog/noi-2009-poet

关于1d1d动归的优化可以看《1d1d动态规划优化初步》

注意可能会爆longlong，所以用extended计算

1 type node=record 2        l,r,x:longint; 3      end; 4  5 var q:array[0..100010] of node; 6     f:array[0..100010] of extended; 7     s:array[0..100010] of longint; 8     x,h,r,i,n,l,p,tt:longint; 9     ss:string;10 11 function pow(x:extended):extended;12   var i:longint;13   begin14     pow:=1;15     for i:=1 to p do16       pow:=pow*x;17   end;18 19 function calc(j,i:longint):extended;20   begin21     exit(f[j]+pow(abs(s[i]-s[j]+i-j-1-l)));22   end;23 24 function max(a,b:longint):longint;25   begin26     if a>b then exit(a) else exit(b);27   end;28 29 function min(a,b:longint):longint;30   begin31     if a>b then exit(b) else exit(a);32   end;33 34 procedure update(i:longint);35   var l,t,m,ans:longint;36   begin37     if calc(i,n)>calc(q[r].x,n) then exit;38     while (i
      
       0 do63   begin64     dec(tt);65     readln(n,l,p);66     s[0]:=0;67     for i:=1 to n do68     begin69       readln(ss);70       x:=length(ss);71       s[i]:=s[i-1]+x;72     end;73     h:=1;74     r:=1;75     q[1].x:=0;76     q[1].l:=1;77     q[1].r:=n;78     for i:=1 to n do79     begin80       while i>q[h].r do inc(h);81       f[i]:=calc(q[h].x,i);82       update(i);83     end;84     if f[i]<=1e18 then writeln(trunc(f[i])) //注意这里trunc不能0:085     else writeln('Too hard to arrange');86     writeln('--------------------');87   end;88 end.