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

Fading

2019-07-26 12:40:36

Solution

没有证明怎么行?我来发一个... ------------ 很显然的 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.}$ #### 因此,原函数满足四边形不等式,得证。 那么直接上单调队列即可。 ```cpp #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; } ```