并不对劲的bzoj1563:p1912:[NOI2009]诗人小G

题目大意

有\(n\)个数\(a_1,...,a_n\)，不改变顺序，把它们划分成若干段。
给定参数\(L,P\)，定义一种划分方案的花费是：每一段的\(|(段内的数的和)+(段内有几个数)-L-1|^P\)之和。
求最小花费的划分方案，若不存在花费不超过\(10^{18}\)的方案则输出无解。\(t\)组数据。
\(t\leq 5;n\leq 10^5;L\leq 10^6;P\leq 10;a_1,...,a_n\leq 30;\)

题解

设\(f(i)\)表示划分第1个词到第i个词的最小花费。
设\(g(i,j)=f(j)+|((j-1)到i这一段的数的和)+(i-j)-L-1|^P\)，则\(f(i)=min{g(i,j)|1\leq j<i}\)。
\([1,k]\)中使\(g(i,j)\)取到最小值的最大的\(j\)，称为\(i\)关于\(k\)的最优决策点。
决策单调性，指\(\forall k\geq 1\)，1到n关于\(k\)的最优决策点有单调性（\(\forall 1\leq i<i‘\leq n\)，\(i\)关于\(k\)的最优决策点都有\(\leq(或都有\geq)i‘\)关于\(k\)的最优决策点）。(1)
对于满足决策单调性的问题，计算\(f(i)\)时可以按最优决策点从小到大用双端队列维护若干个段内最优决策点相同的段。
\(k\)每增加1，就要更新一部分点的最优决策点。由(1)可以知道最优决策点被更新的点是一个后缀。
一个后缀相当于队列尾部的若干（可能为0）个整段，和去掉这些段后，队尾段末的若干（可能是0）个数。
所以每次更新时，先弹出队尾若干个整段，再在队尾段二分被更新的是哪一部分，修改队尾段并从队尾加入新的段。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 100007
#define LD long double
using namespace std;
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!=‘-‘)ch=getchar();
	if(ch==‘-‘)f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();
	return x*f;
}
void write(LL x)
{
	char ch[20];int f=0;
	if(!x){putchar(‘0‘),putchar(‘\n‘);return;}
	if(x<0)putchar(‘-‘),x=-x;
	while(x)ch[++f]=x%10+‘0‘,x/=10;
	while(f)putchar(ch[f--]);
	putchar(‘\n‘);
}
struct node{int x,l,r;}q[maxn];
node mkn(int x,int l,int r){node tmp;tmp.x=x,tmp.l=l,tmp.r=r;return tmp;}
char s[maxn][31];
int t,n,p,frm[maxn],hd,tl;
LD l,f[maxn],sum[maxn];
LD mul(LD x,int y)
{
	LD res=1;
	while(y){if(y&1)res*=x;x*=x,y>>=1;}
	return res;
}
LD Abs(LD x){if(x<0)return -x;return x;}
LD getans(int i,int j)
{
	LD len=sum[i]-sum[j]+(LD)(i-j-1),res=0;len=Abs(len-l);
	return f[j]+mul(len,p);
}
int main()
{
	t=read();
	while(t--)
	{
		n=read(),l=(LD)read(),p=read();hd=1,tl=0;
		rep(i,1,n)scanf("%s",s[i]),sum[i]=sum[i-1]+strlen(s[i]);
		q[++tl]=mkn(0,1,n);int cnt=0; 
		while(hd<=tl)
		{
			cnt++;
			int i=q[hd].l,nxtl=n+1;f[i]=getans(i,q[hd].x);frm[i]=q[hd].x;
			if(i==n)break; 
			q[hd].l++;if(q[hd].l>q[hd].r)hd++;
			while(tl>=hd&&getans(q[tl].l,i)<=getans(q[tl].l,q[tl].x))nxtl=q[tl].l,tl--;
			if(tl>=hd&&getans(q[tl].r,i)<=getans(q[tl].r,q[tl].x))
			{
				int L=q[tl].l,R=q[tl].r;
				while(L<=R)
				{
					int mid=(L+R)>>1;
					if(getans(mid,i)<=getans(mid,q[tl].x))nxtl=min(mid,nxtl),R=mid-1;
					else L=mid+1;
				}
				q[tl].r=nxtl-1;
			}
			if(nxtl!=n+1)tl++,q[tl]=mkn(i,nxtl,n);
		}
		if(f[n]>1e18){puts("Too hard to arrange");}
		else
		{
			write((LL)f[n]);
			int now=1,nxt=frm[n];
			dwn(i,n,1)
			{
				if(i==nxt){now++,nxt=frm[nxt];}
				frm[i]=now;	
			}
			rep(i,1,n)
			{
				printf("%s",s[i]);
				putchar((i==n||frm[i+1]!=frm[i])?‘\n‘:‘ ‘);
			}
		}
		puts("--------------------");
	}
	return (~(0-0)+1);
}

一些感想

这道题中有\((一个很大的数)^{可能是10的数}\)，需要开longdouble。
一开始不想开，想把大于\(10^{18}\)的数当成\(10^{18}+1\)。
这样在更新时，如果新花费和旧花费都大于\(10^{18}\)，一直会有新的花费\(\leq\)旧花费，就会一直更新，这显然是不对的。

并不对劲的bzoj1563:p1912:[NOI2009]诗人小G

原文：https://www.cnblogs.com/xzyf/p/10275505.html