这道题的总体思路是
运用四边形不定式优化dp状态转移
暴力dp是o(n^2);
但是转移的最优解的状态一定具有单调性
这道题里是 单调递增
具体我们就不再证明
也就是说
F[I]=MAX(F[j]+pow(sum[i]-sum[j]+(i-j-1)-l,P))
F具有决策单调性
可以运用四边形不等式优化
四边形不等式优化
额外设一个队列
记录:
1.决策
2.在这个决策下最优的状态转移范围的左边界
3.在这个决策下最优的状态转移范围的右边界
在左边界和右边界之间(包括左边界和右边界)
目前来说
被 与之对应的决策转移 可以得到最优解
那么
维护这样一个队列
上一个的r==下一个的l-1
在转移时实现o(1)
队头出队:
决策的作用范围全部在i之前
队尾入队:
排除不优的决策,如果决策优劣分界线在 决策的作用范围里,二分这个决策优劣分界线,把区间分成两部分,前一部分取原决策,后一部分取现决策,分界线前 原决策优,分界线后 现决策优,把两个三元组按l小–>大放进队列里
需要注意的是:
1.在一开始要放一个0决策
因为从0开始
也就是从第0个到第i个全在一起
这也是一种决策
2.二分时要注意边界
include<bits/stdc++.h>
define ll long double
using namespace std;
int tt;
int n,len,p;
string s;
ll sum[100005];
ll f[100005];
int q[100005][3];
int h,t;
ll ksm(ll a,int b)
{
ll res;
for (res=1;b;a=a,b>>=1) if (b&1) res=a;
return res;
}
ll sol(int j,int i)
{
return f[j]+ksm(abs(sum[i]-sum[j]+i-j-1-len),p);
}
bool cmp(int val,int j,int k)
{
if(sol(j,val)>sol(k,val))
return 1;
return 0;
}
int fen(int l,int r,int i,int j)
{
r;
while(l[HTML_REMOVED]>1;
if(cmp(mid,i,j))
r=mid;
else
l=mid+1;
}
return l;
}
void change(int x)
{
while(h[HTML_REMOVED]l)
{
q[t][0]=val;
q[t][1]=l;
q[t][2]=pos-1;
}
if(pos<=n)
{
q[t][0]=x;
q[t][1]=pos;
q[t][2]=n;
}
}
int main(){
cin>>tt;
while(tt–)
{
memset(sum,0,sizeof(sum));
cin>>n>>len>>p;
for(int i=1;i<=n;i)
{
cin>>s;
sum[i]=s.length()+sum[i-1];
}
h=1;
t=1;
memset(q,0,sizeof(q));
q[1][0]=0;
q[1][1]=1;
q[1][2]=n;
for(int i=1;i<=n;i++)
{
while(h[HTML_REMOVED]1e18)
{
cout<<”Too hard to arrange”<<endl;
cout<<”--------------------“<<endl;
continue;
}
cout<<(long long)f[n]<<endl;
cout<<”--------------------“<<endl;
}
return 0;
}
代码的前后需要放三个`,一个点的话就会被压在一行内了。
谢谢