bzoj1563

思路

首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。

然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制范围)。然后如果当前枚举的位置已经超过队首控制范围。那么队首就可以弹出了。加入新点时，如果队尾控制范围的最左侧也是从当前点转移更优秀，那么队尾就可以弹出了。然后二分当前点与队尾点控制范围的分界点。并且将当前点入队。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long double ll;
const int N=100000+10;
int read() {
                int x=0, tmp=1;
              char ch=getchar();
           //wxywwwwwwwwwwwwwwwwwwww
         while( (ch<'0') || (ch>'9') ){
        if(ch=='-')tmp=-1; ch=getchar();}
         while( (ch>='0')&&(ch<='9') ){
           x=x*10+ch-'0';ch=getchar();
              }//wxywwwwwwwwwwwwwwww
                return (x*tmp);
}
int n;
ll P,Std;
ll f[N],sum[N];
ll qm(ll x) {//快速幂 
    if(x<0) x=-x;
    ll ans=1;
    int y=P;
    for(ll now=x;y;y>>=1,now=now*now)
        if(y&1) ans*=now;
    return ans;
}
ll calc(int x,int y) {//计算函数 
    return f[y]+qm(sum[x]-sum[y]-Std-1);
}
int find(int l,int r,int x,int y) {//二分从l到r中x比y优秀的第一个位置
    int ans=n;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(calc(mid,x)<calc(mid,y)) ans=mid,r=mid-1;
        else l=mid+1;
     }
     return ans;
 }
  
char s[35];
struct node {
    int xh,l,r;
    node () {
        xh=l=r=0;
    }
    node (int x,int L,int R) {
        xh=x,l=L,r=R;
    }
}q[N];
int main() {
    int T=read();
    while(T--) {
        int head=1,tail=0;
        n=read();Std=read();P=read();   
        for(int i=1;i<=n;++i) {
            scanf("%s",s);
            sum[i]=sum[i-1]+strlen(s)+1;
        }
        q[++tail]=node(0,1,n);
        for(int i=1;i<=n;++i) {
            while(head<=tail&&q[head].r<i) head++;//超出队首控制范围 
            f[i]=calc(i,q[head].xh);
            if(calc(n,i) >calc(n,q[tail].xh)) continue;//如果最后一个点都是从队尾转移优秀，那就不用入队了 
            while(head<=tail&&calc(q[tail].l,i)<calc(q[tail].l,q[tail].xh)) tail--;//将队尾出队 
            q[tail].r=find(q[tail].l,n,i,q[tail].xh)-1;//更改控制范围 
            q[++tail]=node(i,q[tail-1].r+1,n);.//入队 
        }
    
        if(f[n]>1e18) puts("Too hard to arrange");
        else
        printf("%lld\n",(long long)f[n]);
        puts("--------------------");
    }
    
    return 0;
}