关于决策单调性
Algha_Porthos
2020-01-20 10:41:25
昨天在Atalod&&网管的帮助下，AC了斜优的板子。那么，现在我要学一学决策单调性。
[P1912](https://www.luogu.com.cn/problem/P1912)，[NOI2009]诗人小G。是一道毒瘤DP。
题意：一首诗，有$n$话。你需要排版。可以把若干句连续的话放在同一行，句间空格隔开，**句末不留空格**。有一个标准长度$l$,以及一个乘方$p$。每一行的贡献是$((\sum_{i=l}^r ss[i].size())+r-l+1)^p$。需要让贡献之和最小。求最小的贡献以及按照最小贡献的排版方式排的任意一种情况。多组数据。$n<=1e5$。
这道题我的$n^2 DP$居然只有10分？？？？
开始决策单调性学习！
对于这一道题，我们显然有$f[i]=min_{0}^{i-1}\ \ f[j]+(abs(l-(s[i]-s[j]-1)))^p$的方程。
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,l,p;
char str[105005][33];
int s[105005];
long double f[105005];
int pr[105005];
long double pw(long double a,long double b){
long double res=1.0;
for(int i=1;i<=b;++i)
res*=a;
return res;
}
void dfs(int u){
if(u==0)
return;
dfs(pr[u]);
for(int i=pr[u]+1;i<u;++i)
cout<<str[i]<<' ';
cout<<str[u]<<endl;
}
int bound(int x,int y){//二分临界值
int l=x,r=n+1,m;//左端点设为x减小常数
while(l<r){
m=(l+r)>>1;
Calc(m,x)>=Calc(m,y)?r=m:l=m+1;
}
return l;
}
long double Calc(int i,int j){
return f[j]+pw(abs(s[i]-s[j]-l-1),p);
}
signed main(){
cin>>T;
for(int _=1;_<=T;++_){
cin>>n>>l>>p;
for(int i=1;i<=n;++i){
scanf("%s",str[i]);
s[i]=s[i-1]+strlen(str[i])+1;
}
int be=1,ed=1;
for(int i=1;i<=n;++i){
int q[105005],k[105005];/////////////////
q[1]=0;
while(be<ed&&k[be]<=i)
++be;
f[i]=Calc(i,q[be]);
pr[i]=q[be];//记录转移位置方便输出方案
while(be<ed&&k[ed-1]>=bound(q[ed],i))
--ed;
k[ed]=bound(q[ed],i);
q[++ed]=i;
}
if(f[n]>1e18)
puts("Too hard to arrange");
else{
printf("%.0Lf\n",f[n]);
dfs(n);
}
puts("--------------------");
}
}
```