[bzoj1563][诗人小g]

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
",(long long)f[n]);
		puts("--------------------");
	}
	
	return 0;
}