【BZOJ 1563】[NOI2009] 诗人小G

题目传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=1563

决策单调性

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LD long double
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 100000+9;
const LD EPS = 1e-8;
const LD MX = 1e18+EPS;

int arr[MAXN],n,L,p,l[MAXN],r[MAXN],que[MAXN],head,tail;
LD f[MAXN];
char pat[50];

inline LD cal(int a, int b){
	return f[b]+pow((LD)abs(arr[a]-arr[b]+a-b-1-L),p);
}

int main(){
	int T; cin>>T;
	while (T--) {
		scanf("%d%d%d",&n,&L,&p);
		for (int i=1;i<=n;i++) scanf("%s",pat+1), arr[i] = arr[i-1] + strlen(pat+1);
		l[head=tail=0] = 1; r[0] = n; f[0] = 0; que[0] = 0;
		for (int i=1;i<=n;i++) {
			while (r[tail] < i) tail++;
			f[i] = cal(i,que[tail]);
			if (cal(r[head],que[head]) < cal(r[head],i)) continue;
			else {
				while (head >= tail && cal(l[head],que[head]) >= cal(l[head],i)) head--;
				if (head >= tail) {
					int ls=l[head],rs=n,ans=0,mid;
					while (ls <= rs) {
						mid = ls + rs >> 1;
						if (cal(mid,que[head]) < cal(mid,i)) ans = mid, ls = mid+1;
						else rs = mid-1;
					}
					r[head] = ans; l[head+1] = ans+1; r[head+1] = n;
				} else l[head+1] = 1, r[head+1] = n;
				que[++head] = i; 
			}	
		}
		if (f[n] <= MX) printf("%lld\n",(LL)(f[n]+EPS));
		else printf("Too hard to arrange\n");
		puts("--------------------");
	}
	return 0;
}