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

· · 题解

没有证明怎么行？我来发一个...

很显然的 dp 方程：

f_i=\min(f_j+|\text{sum}_i-\text{sum}_j+i-j-1-L|^P)

其中

\text{sum}_x=\sum_{i=1}^xa_i

如果这个状态转移方程是决策单调的，那么可以直接上单调队列。

但是怎么证明呢？

我们只需证明函数G_j(i)=|\text{sum}_i+i-(\text{sum}_j+j)-(1+L)|^P满足四边形不等式。

\Leftrightarrow\ G_j(i+1)+G_{j+1}(i)\geq G_{j}(i)+G_{j+1}(i+1)

尝试把左右两边统一化，简化式子，表示G_{j},G_{j+1}

设

u=\text{sum}_i+i-(\text{sum}_j+j)-(1+L),v=\text{sum}_i+i-(\text{sum}_j+a[j]+j+1)-(1+L)

则

\Leftrightarrow |u+1+a_{i+1}|^P+|v|^P\geq |u|^P+|v+1+a_{i+1}|^P \Leftrightarrow |v|^P-|v+a_{i+1}+1|^P\geq |u|^P-|u+a_{i+1}+1|^P \because\ u>v

所以原问题等价于证明h(x)=|x|^P-|x+z|^P(z\in [0,\infty))非严格单调递减。

注意到有绝对值，我们分类讨论。

当x\in[0,\infty):

h(x)=x^P-(x+z)^P h'(x)=Px^{P-1}-P(x+z)^{P-1} =Px^{P-1}-P\sum_{i=0}^{P-1}C_{P-1}^ix^{P-i-1}z^i =-P\sum_{i=1}^{P-1}C_{P-1}^ix^{P-i-1}z^i

由于z\geq 0,x\in[0,\infty),\therefore h'(x)\leq0,\text{Q.E.D.}

当x\in(-\infty,0),P\equiv0\pmod 2:

h(x)=x^P-(x+z)^P

证明过程同第一种情况，此处省略。

当x\in[-z,0),P\equiv1\pmod 2:

h(x)=-x^P-(x+z)^P h'(x)=-Px^{P-1}-P(x+z)^{P-1}

由于x^{P-1}恒大于0，\therefore h'(x)\leq0,\text{Q.E.D.}

当x\in(-\infty,-z),P\equiv1\pmod 2:

h(x)=-x^P+(x+z)^P h'(x)=-Px^{P-1}+P(x+z)^{P-1} h'(x)=-P(x^{P-1}-(x+z)^{P-1})

显然x^{P-1}>(x+z)^{P-1}，因为这是一个偶函数。

所以h'(x)\leq 0,\text{Q.E.D.}

因此，原函数满足四边形不等式，得证。

那么直接上单调队列即可。

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
long double dp[500201];
ll L,P,n,ans[500021],a[500201],sum[500201],dl[500201],hd,ta;
inline long double fast_pow(long double a,ll b){
    long double t=1;
    while (b){
        if (b&1LL) t=t*a;
        b>>=1LL;a=a*a;
    }
    return t;
}
inline long double calc(int i,int x){
    return dp[i]+fast_pow(abs(sum[x]-sum[i]+x-i-1-L),P);
}
inline int get(int a,int b){
    if (calc(a,n)<calc(b,n)) return n+1;
    int lb=b,rb=n,ans=-1;
    while (lb<=rb){
        int mid=(lb+rb)>>1;
        if (calc(b,mid)<=calc(a,mid)) ans=mid,rb=mid-1;
        else lb=mid+1;
    }
    return ans;
}
int sta[100202],T;
char s[102002][32];
signed main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while (T--){
        cin>>n>>L>>P;
        for (int i=1;i<=n;i++){
            cin>>s[i];a[i]=strlen(s[i]);sum[i]=sum[i-1]+a[i];
            ans[i]=0;dp[i]=1e19;
        }
        hd=1,ta=1;
        for (int i=1;i<=n;i++){
            while (hd<ta&&get(dl[hd],dl[hd+1])<=i) hd++;
            ans[i]=dl[hd];dp[i]=calc(dl[hd],i);
            while (hd<ta&&get(dl[ta-1],dl[ta])>=get(dl[ta],i)) ta--;
            dl[++ta]=i;
        }
        if (dp[n]>1e18){
            puts("Too hard to arrange");
        }else{
            printf("%lld\n",(long long)dp[n]);
            int top=0;
            for (int tmp=n;tmp;tmp=ans[tmp]) sta[++top]=tmp;
            sta[++top]=0;
            for (int i=top;i>1;i--){
                for (int j=sta[i]+1;j<sta[i-1];j++){
                    printf("%s ",s[j]);
                }
                printf("%s",s[sta[i-1]]); 
                printf("\n");
            }
        }
        puts("--------------------");
    }
    return 0;
}