对于很多决策单调性DP问题，我们很难（但不是不可以）证明其决策满足单调性，所以感觉很像时，可以打表看是否满足。
这道题的精度（？范围）很难搞，开始生怕溢出，看了hzwer的代码，才发现用long double，因为这道题只有乘法，没有除法，并且long double的保存系数的那部分还是挺大的（好像有效位数是64位）。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)<0?-(a):(a))
#define mdp 1000000000000000000LL
#define N 100010 typedef long double ddt; struct Trid {
int p, l, r;
Trid(){}
Trid( int p, int l, int r ):p(p),l(l),r(r){}
}; int n, len, pw;
int w[N], sw[N], f[N];
ddt dp[N];
Trid stk[N]; int top; ddt pow( int a, int b ) {
ddt rt = ;
for( int i=; i<=b; i++ )
rt *= a;
return rt;
}
ddt getw( int j, int i ) {
return pow(abs(sw[i]-sw[j-]+i-j-len), pw);
}
ddt calc( int j, int i ) {
ddt rt = dp[j-]+getw(j,i);
if( rt< ) {
fprintf( stderr, "Overflow\n" );
exit();
}
return rt;
}
ddt dodp() {
stk[top=] = Trid( , , n );
dp[] = calc(,);
for( int i=; i<=n; i++ ) {
if( calc(stk[top].p,n)>calc(i,n) ) {
while( stk[top].l>=i && calc(stk[top].p,stk[top].l)>calc(i,stk[top].l) )
top--;
if( stk[top].r==i- ) {
stk[++top] = Trid( i, i, n );
} else {
int lf=max(stk[top].l+,i);
int rg=min(stk[top].r+,n);
while(lf<rg) {
int mid=(lf+rg)>>;
if( calc(stk[top].p,mid)>calc(i,mid) )
rg = mid;
else
lf = mid+;
}
stk[top].r = lf-;
stk[++top] = Trid( i, lf, n );
}
}
int lf=, rg=top;
while(lf<rg) {
int mid=(lf+rg+)>>;
if( stk[mid].l>i ) rg=mid-;
else lf=mid;
}
dp[i] = calc(stk[lf].p,i);
}
return dp[n];
}
int main() {
int T;
scanf( "%d", &T );
while( T-- ) {
scanf( "%d%d%d", &n, &len, &pw );
for( int i=; i<=n; i++ ) {
char buf[];
scanf( "%s", buf );
w[i] = strlen(buf);
sw[i] = sw[i-]+w[i];
}
ddt ans=dodp();
if( ans>mdp )
printf( "Too hard to arrange\n" );
else
printf( "%lld\n", (long long)ans );
printf( "--------------------\n" );
}
}