P1912 [NOI2009] 诗人小G

题目链接
题解：
定义
算上空格的前缀和\(sum[i]=\sum_{j=1}^{i}len[j]+1\)
\(dp[i]=min_{j<i}(dp[j]+|sum[i]-sum[j]-1+L|^p)\)
相当于枚举上一行的结尾在哪。
可以感性理解一下，i越靠后，最优决策点j一定会往后移。
所以决策点具有单调性。我有一个简单的证明，就是列个式子，证明i向后移一位，用j转移的式子一定小于用j-1转移。
然后，维护决策单调性，这道题不能直接用分治算法(好像可以cdq,但我不会)，所以我们用二分队列来做。
首先遍历到一个点先计算它的\(dp[i]\)，考虑队列中维护的是一个从小到大没有交集的一段区间的最优决策点。所以找到区间包含i的元素，转移即可。
然后更新转移点，显然我们可以通过二分确定(只考虑前面i个点)这点作为最佳决策点的区间，记录左端点，右端点直接当作\(n+1\)。将被完全覆盖的区间的最佳决策点弹出去（一定不如i）。最后入栈即可。
注意事项：\(1e18\) 用\(long long\)很危险，所以用\(long\) $double $来存牺牲一点精度。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,L,P,l[N],sum[N],q[N],ans[N],opt[N];
long double dp[N];
string s[N]; 
long double ksm(long double x,int y)
{
	long double an=1;
	while(y)
	{
		if(y&1)an=an*x;
		y>>=1;
		x=x*x;
	}
	return an;
}
long double js(int j,int i)
{
	return dp[j]+ksm((long double)abs(sum[i]-sum[j]-1-L),P);
}
int find(int x,int y)
{
	int l=x,r=n+1,an=n+1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(js(x,mid)<js(y,mid))l=mid+1;
		else an=mid,r=mid-1;
	}
	return an;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>L>>P;
		for(int i=1;i<=n;i++)
		{
			sum[i]=0;
			cin>>s[i]; 
			sum[i]=sum[i-1]+s[i].size()+1;
		}
		int head=1,tail=1;q[1]=0;
		for(int i=1;i<=n;i++)
		{
			while(head<tail&&l[head]<=i)head++;//l记录下一区间的左端点即当前区间的最大值
			opt[i]=q[head];
			dp[i]=js(q[head],i);
			while(head<tail&&l[tail-1]>=find(q[tail],i))tail--;
			l[tail]=find(q[tail],i);
			q[++tail]=i; 
			//printf("%d %lld %d %d\n",opt[i],(long long)dp[i],l[tail-1],q[tail]);
		}
		if(dp[n]>1e18)cout<<"Too hard to arrang"<<'\n';
		else
		{
			cout<<(long long)dp[n]<<'\n'; 
			int x=n,cnt=0;
			ans[++cnt]=n;
			while(x!=0)
			{
				x=opt[x];
				ans[++cnt]=x;
			}
			for(int i=cnt;i;i--)
			{
				for(int j=ans[i]+1;j<=ans[i-1];j++)
				{
					cout<<s[j];
					if(j!=ans[i-1])cout<<' ';
				}		
				if(i!=1)cout<<'\n';					
			}				
		}
		cout<<"--------------------";if(t)cout<<'\n';
	}
	return 0;
 }