Luogu

分析

设 $dp_i$ 表示前 $i$ 句诗的最小不协调度,$sum_i=i+\sum_{j=1}^ilen_i$,容易写出状态转移方程

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+|sum_i-sum_j-1-L|^P\right\} $$

我们令 $f_i(x)=dp_i+|sum_x-sum_i-1-L|^P$,可以发现 $f_i(x)$ 是关于 $sum_i-1-L$ 对称的,而且每个 $f_i(x)$ 的形状都一样。再进一步,这个 DP 是具有决策单调性的。

那么只需要用单调队列维护一下就好了,具体做法和这个题是一样的...

然后这题有一些要注意的地方:

  • 答案会爆 long long,请开 long double
  • 自带的 pow 非常慢还掉精度,请手写一个快速幂。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,l,p; char s[N][35];
int sum[N],pre[N],vis[N]; long double dp[N];
int Q[N],k[N],h,t;

inline long double qpow(long double a,int b) { long double c=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}
inline long double calc(int i,int x) {
    return dp[i]+qpow(abs(sum[x]-sum[i]-1-l),p);
}
inline int find(int i,int j) {
    int L=i,R=n+1;
    while (L<R) {
        int mid=(L+R)>>1;
        if (calc(i,mid)>=calc(j,mid)) R=mid;
        else L=mid+1;
    }
    return L;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),l=read(),p=read();
        for (re int i=1;i<=n;++i) {
            scanf("%s",s[i]+1);
            sum[i]=sum[i-1]+strlen(s[i]+1)+1;
        }
        Q[h=t=1]=0;
        for (re int i=1;i<=n;++i) {
            while (h<t&&k[h]<=i) ++h;
            dp[i]=calc(Q[h],i),pre[i]=Q[h];
            while (h<t&&k[t-1]>=find(Q[t],i)) --t;
            k[t]=find(Q[t],i),Q[++t]=i;
        }
        if (dp[n]>1e18) puts("Too hard to arrange");
        else {
            printf("%.0Lf\n",dp[n]);
            for (re int i=1;i<=n;++i) vis[i]=0;
            for (re int i=n;i;i=pre[i]) vis[i]=1;
            for (re int i=1;i<=n;++i)
                printf("%s%c",s[i]+1," \n"[vis[i]]);
        }
        puts("--------------------");
    }
    return 0;
}
最后修改:2019 年 10 月 23 日 09 : 02 PM