题解 P1912 【[NOI2009]诗人小G】

n个数划分若干段，给定$L$,$p$，每段代价为$|sum_i-sum_j-1-L|^p$，求总代价最小。 正常的dp决策单调性优化题目。$f[i]$表示最小代价。然后有个正常的dp方程。 $f[i]=min \{ f[j]+|sum_i-sum_j-1-L|^p \} $ 然后观察发现带高次项，不好斜率优化或单调队列，考虑有没有决策单调性。本来是可以打表证明的，然后拍一下。~~题解没人证单调性，于是我来瞎证一波，有错别怪我。~~ 证明： 已知$f[j]+|sum_i-sum_j-1-L|^p < f[j']+|sum_i-sum_{j'}-1-L|^p$ 要证$f[j]+|sum_i-sum_j-L|^p < f[j']+|sum_i-sum_{j'}-L|^p$ $(j'<j)$(就是$i$加了$1$) 即证 $|sum_i-sum_{j'}-1-L|^p+|sum_i-sum_j-L|^p < |sum_i-sum_j-1-L|^p+|sum_i-sum_{j'}-L|^p$ 即$|sum_i-sum_{j'}-1-L|^p-|sum_i-sum_{j'}-L|^p < |sum_i-sum_j-1-L|^p-|sum_i-sum_j-L|^p$ 然后把其看成关于j的函数，或者就把$S_i-S_j-L$看成$x$简便一些，$j$增大，$S_j$增大，$x$总的减小。下面看单调性。可能证的**不太严谨**，有问题还望指教。 $f(x)=|x-1|^p-|x|^p$ (p为大于2正整数) ①$p$为偶数,则$f(x)=(x-1)^p-x^p$ $f'(x)=p(x-1)^{p-1}-px^{p-1}$ $x>=1$时显然小于$0$，此段单调减 $0<=x<1$时$p(x-1)^{p-1}<px^{p-1}$即$p(x-1)^{p-1}-px^{p-1}<0$，此段单调减 $x<0$时也有上述关系。 又因为$x∈R$内函数值是连续（就是几个转折点值在左右边两个范围内算出来的f都一样的）的，所以整个是一直单调减的。 ②$p$为奇数,$p-1$为偶,则 $x>=1$时$f'(x)=p(x-1)^{p-1}-px^{p-1}<0$单调减 $0<=x<1$时$f(x)=(1-x)^p-x^p$,则$f'(x)=-p(x-1)^{p-1}-px^{p-1}<0$因为偶数次方必定大于0嘛 $x<0$时$f(x)=(1-x)^p+x^p$ ，$f'(x)=-p(x-1)^{p-1}+px^{p-1}$ $∵x-1<x<0$ $∴(x-1)^{p-1}>x^{p-1}$ $∴f'(x)=-p(x-1)^{p-1}+px^{p-1}<0$ $综上，p为奇或偶都有导数小于0，f随x单调减，j增大，S_j增大,x减小，f必然增大，则原不等式得证。$ $所以满足决策单调性。$ $证毕。$ 好像有漏洞？算了不管了。希望各位能指出或完善证明，因为我其实根本就不会求导。**~~而且我的数学差的要死，全班倒数。~~** 然后随便套套决策单调性模板就行啦，这个可以去看以及膜上下楼的比我强了几百万倍的julao。 注意一下要用long double范围大，不然long long会爆。注意不用刻意考虑和判断会不会爆，正常用long double虽然牺牲精度但毕竟还是总体大于$10^{18}$的。 ```cpp #include<bits/stdc++.h> #define dbg(x) cerr<<#x<<"="<<x<<endl using namespace std; typedef long double ll; typedef double db; template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} template<typename T>inline T _min(T A,T B){return A<B?A:B;} template<typename T>inline T _max(T A,T B){return A>B?A:B;} template<typename T>inline T read(T&x){ x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; } inline ll fpow(ll x,int p){ll ret=1;for(;p;p>>=1,x=x*x)if(p&1)ret=ret*x;return ret;} inline int Abs(int x){return x>0?x:-x;} const int N=100000+7;ll INF=1e18; struct thxORZ{ int l,r,pos; thxORZ(int l0=0,int r0=0,int pos0=0):l(l0),r(r0),pos(pos0){} }q[N]; char s[N][32]; ll f[N],lim; int sum[N],pre[N]; int T,L,p,n,l,r; inline ll calc(int j,int i){return f[j]+fpow(Abs(sum[i]-sum[j]-1-L),p);} inline int find_pos(int L,int R,int j,int i){ int mid; while(L<R){ mid=L+R>>1; if(calc(j,mid)>=calc(i,mid))R=mid; else L=mid+1; } return R; } inline void dp(){ q[l=r=1]=thxORZ(1,n,0); for(register int i=1;i<=n;++i){ f[i]=calc(q[l].pos,i);pre[i]=q[l].pos;//dbg(i),dbg(f[i]),dbg(sum[i]); if(i==q[l].r)++l;else ++q[l].l; if(f[i]>INF)continue;//小优化：当前状态如果已经无效就不要更新决策表了。 while(l<=r&&calc(q[r].pos,q[r].l)>=calc(i,q[r].l))--r; if(r<l)q[r=l]=thxORZ(i+1,n,i); else{ int k;if(calc(q[r].pos,q[r].r)<=calc(i,q[r].r))k=q[r].r+1; else k=find_pos(q[r].l,q[r].r,q[r].pos,i);//dbg(i),dbg(k); if(k<=n)q[r].r=k-1,q[++r]=thxORZ(k,n,i); } } } inline void print(int x,int y){ if(x)print(pre[x],x); for(register int i=x+1;i<=y;++i)printf("%s",s[i]),i==y?putchar('\n'):putchar(' '); } int main(){//freopen("test.in","r",stdin);freopen("tmp.out","w",stdout); read(T);while(T--){ read(n),read(L),read(p);lim=(ll)ceil(pow(1e18,1.0/(db)p)); for(register int i=1;i<=n;++i)scanf("%s",s[i]),sum[i]=sum[i-1]+strlen(s[i])+1; dp();if(f[n]>INF)printf("Too hard to arrange\n"); else printf("%lld\n",(long long)f[n]),print(pre[n],n); printf("--------------------\n"); } return 0; } ```