[洛谷 1912][NOI2009]诗人小G

题目链接

https://www.luogu.org/problem/P1912

题解

（填上了自己之前挖的大坑.webp）

为了方便起见，我们给每个字符串后面加一个空格。

和 [HNOI2008]玩具装箱 一样，我们设 \(s_i\) 为字符串长度前缀和，\(f_i\) 为前 \(i\) 个字符串的最小不协调度。

显然有如下转移方程：

$$f_i=\min_{1 \leq j < i} f_j+|s_j-s_i-1-l|^p$$

这时候的 \(p\) 不再是之前的 \(2\)，不能用斜率优化。

考虑证明决策单调性。

当然可以用四边形不等式，不过要偷懒的话打表观察一下决策点递变规律也行。

证明了决策单调性后就可以维护单调队列，二分寻找决策最优点即可。

需要注意的是，答案可能无法用 64 位整数存储，但 double 的精度并不一定够，需要用 long double。

#include <cstring>
#include <iostream>
using namespace std;
char s[100005][35];
int sum[100005],q[100005],pt[100005],res[100005],ans[100005];
int n,l,p;
long double f[100005];
long double fpow(long double x,int y)
{
 long double ans=1;
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
long double calc(int x,int y)
{
 return f[x]+fpow(abs(sum[y]-sum[x]-1-l),p);
}
int find(int x,int y)
{
 int l=x,r=n+1;
 while(l<r)
 {
  int mid=(l+r)>>1;
  if(calc(x,mid)>=calc(y,mid))r=mid;
  else l=mid+1;
 }
 return l;
}
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  cin>>n>>l>>p;
  for(int i=1;i<=n;i++)
  {
   cin>>s[i];
   sum[i]=sum[i-1]+strlen(s[i])+1;
  }
  memset(q,0,sizeof(q));
  int l=0,r=0;
  for(int i=1;i<=n;i++)
  {
   while(l<r&&pt[l]<=i)
    l++;
   f[i]=calc(q[l],i);
   res[i]=q[l];
   while(l<r&&pt[r-1]>=find(q[r],i))
    r--;
   pt[r]=find(q[r],i);
   q[++r]=i;
  }
  if(f[n]>1e18)cout<<"Too hard to arrange"<<endl;
  else
  {
   cout<<(long long)f[n]<<endl;
   int cnt=0;
   ans[0]=n;
   for(int i=n;i;i=res[i])
    ans[++cnt]=res[i];
   for(int i=cnt;i;i--)
   {
    for(int j=ans[i]+1;j<ans[i-1];j++)
     cout<<s[j]<<' ';
    cout<<s[ans[i-1]]<<endl;
   }
  }
  cout<<"--------------------"<<endl;
 }
 return 0;
}