【Luogu1912】【NOI2009】诗人小G（动态规划）

题面

题解

原来(NOI)这么多神仙题。。。
考虑一个极其明显的(dp)
设(f[i])表示前(i)个句子产生的最小代价
转移也很显然，就懒得写了。
仔细思考一下，转移具有单调性。
但是我们用单调队列似乎无法直接维护。
继续思考一下，我们的转移结果一定是从前面一个位置转移过来的
并且一定是一段连续的位置都由那个位置转移过来。
同时，如果(i)从(j)转移过来，(i+1)从(k)转移过来，其中(j<k)
那么，一定不存在(x>i)，使得(x)从(j)转移。
因此决策也具有单调性。
所以利用一个单调队列来维护一下决策的单调性。
维护一下当前点影响的范围。
每次插入新点的时候，这个点影响的范围一定是一个位置(x)到(n)
所以二分一下这个位置就好了
时间复杂度(O(Tnlognlogp))，复杂度来自于二分+快速幂
~~又一次成为了cin/cout选手~~

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 111111
#define double long double
struct Node{int j,l,r;}Q[MAX];
int a[MAX],n,L,P,h,t,g[MAX],S[MAX],top;
string ch[MAX];
double f[MAX];
ll s[MAX];
double fpow(double a,int b)
{
	double s=1;
	while(b){if(b&1)s*=a;a*=a;b>>=1;}
	return s;
}
double Calc(int i,int j){return f[j]+fpow(fabs(s[i]-s[j]-1-L),P);}
int main()
{
	ios::sync_with_stdio(false);
	int T;cin>>T;
	while(T--)
	{
		cin>>n>>L>>P;
		for(int i=1;i<=n;++i){cin>>ch[i];a[i]=ch[i].length();}
		for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i]+1;
		memset(Q,0,sizeof(Q));
		Q[h=t=1]=(Node){0,1,n};
		for(int i=1;i<=n;++i)
		{
			while(h<t&&Q[h].r<i)++h;
			int j=Q[h].j;Q[h].l++;
			f[i]=Calc(i,j);g[i]=j;
			while(h<t&&Calc(Q[t].l,Q[t].j)>=Calc(Q[t].l,i))--t;
			int l=Q[t].l,r=Q[t].r,ret=Q[t].r+1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(Calc(mid,i)<=Calc(mid,Q[t].j))ret=mid,r=mid-1;
				else l=mid+1;
			}
			if(ret!=Q[t].l)Q[t].r=ret-1;else --t;
			if(ret<=n)Q[++t]=(Node){i,ret,n};
		}
		if(f[n]>1e18)cout<<"Too hard to arrange"<<endl;
		else
		{
			cout<<(ll)f[n]<<endl;
			top=0;
			for(int i=n;i;i=g[i])S[++top]=i;S[top+1]=0;
			for(int i=top;i;--i)
				for(int j=S[i+1]+1;j<=S[i];++j)
				{
					cout<<ch[j];
					if(j!=S[i])cout<<' ';
					else cout<<endl;
				}
		}
		cout<<"--------------------"<<endl;
	}
	return 0;
}