这道题的DP式长这样
$f_i=\min\{f_j+(s_i-s_j+(i-j+1)-L)^p\}$
高次的东西一般都不能斜率优化,因此考虑四边形不等式,
但是这道题的四边形不等式要用到求导,所以咕了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<cstdlib>
#define ll long long
#define ld long double
#define gc getchar()
using namespace std;
const int N=1e5+10;
template<class o>
inline void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
vector<string>ss;
char tmp[N];
ld f[N];ll s[N];int L,p,prv[N];
ld calc(int j,int i)
{
ld ans=1,num=abs(s[i]-s[j]+(i-j-1)-L);
int b=p;
while(b)
{
if(b&1)ans*=num;
b>>=1;num*=num;
}
return f[j]+ans;
}
struct node{int p,l,r;}q[N];
void pri(int n)
{
if(!n)return ;
pri(prv[n]);
for(int i=prv[n]+1;i<n;i++)
cout<<ss[i]<<' ';
cout<<ss[n];
puts("");
}
int main()
{
//freopen("testdata (1).in","r",stdin);
//freopen("1.out","w",stdout);
int T;qr(T);
while(T--)
{
int n;qr(n),qr(L),qr(p);s[0]=0;
ss.clear();ss.push_back("lb");
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
ss.push_back(tmp);
s[i]=1ll*strlen(tmp),s[i]+=s[i-1];
}
int l=1,r=1;q[1]=(node){0,1,n};
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
f[i]=calc(q[l].p,i);
prv[i]=q[l].p;
if(q[l].r==i)++l;
else q[l].l=i+1;
int pos=n+1;
while(l<=r)
{
node &a=q[r];
if(calc(a.p,a.l)>=calc(i,a.l)){--r;pos=a.l;}
else if(calc(a.p,a.r)<calc(a.p,a.r))break;
else
{
int pl=a.l,pr=a.r;
while(pl<pr)
{
int mid=pl+pr+1>>1;
if(calc(a.p,mid)>=calc(i,mid))pr=mid-1;
else pl=mid;
}
a.r=pr;pos=pr+1;
break;
}
}
if(pos!=n+1)q[++r]=(node){i,pos,n};
}
if(f[n]>1e18)puts("Too hard to arrange");
else
{
qw((ll)f[n]),puts("");
pri(n);
}
puts("--------------------");
}
return 0;
}
最后一次更新于2019-11-01
0 条评论