关于决策单调性

2020-01-20 10:41:25


昨天在Atalod&&网管的帮助下,AC了斜优的板子。那么,现在我要学一学决策单调性。

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("--------------------");
    }
}