P1912 [NOI2009]诗人小G 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • bztMinamoto
    大佬写的很清楚顺便fjtAKNOI
  • littleming
    请问max能用决策单调性吗(我看的证明里面好像只能用min)
  • FlashHu
    @littleming 蒟蒻写的好像是有问题,决策单调性的定义是决策点递增,而把min换成max只是满足编号大的决策函数在x足够大的时候一定会被编号小的决策函数取代,而决策点好像并没有什么顺序
  • 小乐
    Orz...
  • yuyue
    为什么是Calc(m,x)>=Calc(m,y)而不是Calc(x,m)>=Calc(y,m),虽然前者是正确的
  • yuyue
    请原谅我zz了
  • 绫韵华音
    大佬能讲一下二分的时候,为什么右边界要 + 1么(蒟蒻瑟瑟发抖——————)
  • command_block
    %%%
  • WAutomaton
    代码注释完美避开了所有关键变量
  • WAutomaton
    终于看懂了...其实和斜率优化差不多...
作者: FlashHu 更新时间: 2018-08-22 23:30  在Ta的博客查看 举报    28  

闲话

看完洛谷larryzhong巨佬的题解,蒟蒻一脸懵逼

如果哪年NOI(放心我这样的蒟蒻是去不了的)又来个决策单调性优化DP,那蒟蒻是不是会看都看不出来直接爆$0$?!

还是要想点办法,不失一般性也能快捷地判定决策单调。

对于判定决策单调的分析

再补一句决策单调性的概念:状态转移方程形如$f_i=\min/\max_{j=1}^{i-1} g_j+w_{i,j}$,且记$f_i$的最优决策点为$p_i$(也就是$f_i$从$g_{p_i}+w_{i,p_i}$处转移最优)若满足$p_i\le p_{i+1}$,则该方程满足决策单调性。(摘自蒟蒻的DP优化总结

显然每个决策$j$可以用一个关于$i$的函数$f_j(i)$表示。

函数的一个重要思想:数形结合!

光靠脑子想不到规律,只好先举一些用语言难以描述的反例。我们的函数不能这样

看到这里Dalao们有没有一点想法呢?蒟蒻反正想到了一点——两个函数必须只有一个交点!在这一点之前一个函数更优,而之后就被永远取代了。

感觉满足条件的函数其实很少,分类讨论一下(如有误欢迎Dalao指教)

直线

显然上面的基本要求都满足。不过要是函数是直线的话都可以用斜率优化搞了($k_1x+b_1\ge k_2x+b_2,x\ge\frac{b_2-b_1}{k_1-k_2}$)。

不是直线

为了避免图1的尴尬情况,可能需要所有决策函数之间可以通过平移相互变换(形如$f_j(x)=f_k(x-a)+b$)。

为了避免图2的尴尬情况,可能需要函数的导函数在各自的定义域内单调递增/递减(注意是导函数不是原函数)。

接着,根据蒟蒻肝过的几个题,好像还有一条规律——

如果导函数递增、求最大值(柠檬),或者导函数递减、求最小值,要用单调栈。

如果导函数递增、求最小值(本题),或者导函数递减、求最大值(Lightning Conductor),要用单调队列。

复杂的函数

蒟蒻见过这一道(Yet another minimization problem

感觉可以看成对于每一种数都有一个函数$\frac{(c_i-c_j)(c_i-c_j+1)}{2}$,单看这一个是满足决策单调性的($c_i\ge c_j$,定义域内的导函数是递增的)。

那么总函数就可以写成$f_j(i)=g_j+\sum\frac{(c_i-c_j)(c_i-c_j+1)}{2}$,怎么看也不像是不满足决策单调性的。

本题的思路

那么就可以回归本题了。

设$len_i$为第$i$句的长度,$s_i=i+\sum\limits_{j=1}^i len_j$(加上$i$是默认一句话后面有空格)

设$f_i$为选前$i$句的最小代价,我们枚举当前这一行填入最后面的多少个句子,注意行末没有空格,长度要$-1$,那么有方程

$$f_i=\min\limits_{j=0}^{i-1}\{f_j+|s_i-s_j-1-L|^P\}$$

容易发现后面这一坨决策函数是关于直线$x=s_j+1+L$对称的。把它去绝对值,变成两段,显然左边一段和右边一段的导函数都是递增的,左边恒$<0$,右边恒$>0$。又因为这函数是连续的,所以当然整个函数的导函数也单调递增咯!

用队列维护决策二分栈的过程不再赘述,总结里也有。时间复杂度$O(Tn\log n)$

看到Dalao们都记录了一个三元组,可蒟蒻还是觉得没啥必要啊。。。只要保存队列中相邻两个元素的临界值$k$就好了吧。

一个写法技巧:

二分决策$x,y(x<y)$的临界值的时候,左端点设成$x$就好了,没必要设成$1$(难怪蒟蒻之前写Lightning Conductor跑得有点慢)

三个坑点:

不管是转移还是输出,都要去掉行末的空格(怪蒟蒻看题不清)

当答案大于$10^{18}$的时候开longlong也炸了,所以要用实数以牺牲精度的代价换来更大的值域。然而double真的WA了。于是要开long double。

cmath的pow太慢了容易TLE,要手写快速幂。

#include<cstdio>
#include<cmath>
#include<cstring>
#define RG register
#define R RG int
#define G c=getchar()
#define Calc(i,j) f[j]+qpow(abs(s[i]-s[j]-L))//计算函数值
using namespace std;
typedef long double LD;//开long double
const int N=1e5+9;
int n,L,P,s[N],q[N],k[N],pr[N];
LD f[N];
char str[N][33];
inline int in(){
    RG char G;
    while(c<'-')G;
    R x=c&15;G;
    while(c>'-')x*=10,x+=c&15,G;
    return x;
}
inline LD qpow(RG LD b){//自己写快速幂
    RG LD a=1;
    for(R k=P;k;k>>=1,b*=b)
        if(k&1)a*=b;
    return a;
}
inline int bound(R x,R y){//二分临界值
    R 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;
}
int main(){
    R T=in(),i,h,t;
    while(T--){
        n=in();L=in()+1;P=in();//把L处理了一下
        for(i=1;i<=n;++i){
            if(scanf("%s",str[i]));
            s[i]=s[i-1]+strlen(str[i])+1;//记前缀和
        }
        for(q[i=h=t=1]=0;i<=n;++i){
            while(h<t&&k[h]<=i)++h;
            f[i]=Calc(i,q[h]);pr[i]=q[h];//记录转移位置方便输出方案
            while(h<t&&k[t-1]>=bound(q[t],i))--t;
            k[t]=bound(q[t],i);q[++t]=i;
        }
        if(f[n]>1e18)puts("Too hard to arrange");
        else{
            printf("%.0Lf\n",f[n]);
            for(q[t=0]=i=n;i;q[++t]=i=pr[i]);
            for(;t;--t){
                for(i=q[t]+1;i<q[t-1];++i)
                    printf("%s ",str[i]);
                puts(str[i]);//行末不要搞空格
            }
        }
        puts("--------------------");
    }
    return 0;
}

评论

  • ACAね
    讲的很好
作者: Fading  更新时间: 2019-07-26 12:40  在Ta的博客查看 举报    9  

没有证明怎么行?我来发一个...


很显然的$dp$方程:

$$f_i=min(f_j+|sum_i-sum_j+i-j-1-L|^P)$$

其中 $$sum_x=\sum_{i=1}^xa_i$$

如果这个状态转移方程是决策单调的,那么可以直接上单调队列。

但是怎么证明呢?

我们只需证明函数$G_j(i)=|sum_i+i-(sum_j+j)-(1+L)|^P$满足四边形不等式。

$$\Leftrightarrow\ G_j(i+1)+G_{j+1}(i)\geq G_{j}(i)+G_{j+1}(i+1)$$

尝试把左右两边统一化,简化式子,表示$G_{j},G_{j+1}$

$$u=sum_i+i-(sum_j+j)-(1+L),v=sum_i+i-(sum_j+a[j]+j+1)-(1+L)$$

$$\Leftrightarrow |u+1+a_{i+1}|^P+|v|^P\geq |u|^P+|v+1+a_{i+1}|^P$$

$$\Leftrightarrow |v|^P-|v+a_{i+1}+1|^P\geq |u|^P-|u+a_{i+1}+1|^P$$

$$\because\ u>v$$

所以原问题等价于证明$h(x)=|x|^P-|x+z|^P(z\in [0,\infty))$非严格单调递减。

注意到有绝对值,我们分类讨论。

当$x\in[0,\infty):$

$$h(x)=x^P-(x+z)^P$$

$$h'(x)=Px^{P-1}-P(x+z)^{P-1}$$

$$=Px^{P-1}-P\sum_{i=0}^{P-1}C_{P-1}^ix^{P-i-1}z^i$$

$$=-P\sum_{i=1}^{P-1}C_{P-1}^ix^{P-i-1}z^i$$

由于$z\geq 0,x\in[0,\infty),\therefore h'(x)\leq0,Q.E.D.$

当$x\in(-\infty,0),P\equiv0\pmod 2:$

$$h(x)=x^P-(x+z)^P$$

证明过程同第一种情况,此处省略。

当$x\in[-z,0),P\equiv1\pmod 2:$

$$h(x)=-x^P-(x+z)^P$$

$$h'(x)=-Px^{P-1}-P(x+z)^{P-1}$$

由于$x^{P-1}$恒大于$0$,$\therefore h'(x)\leq0,Q.E.D.$

当$x\in(-\infty,-z),P\equiv1\pmod 2:$

$$h(x)=-x^P+(x+z)^P$$

$$h'(x)=-Px^{P-1}+P(x+z)^{P-1}$$

$$h'(x)=-P(x^{P-1}-(x+z)^{P-1})$$

显然$x^{P-1}>(x+z)^{P-1}$,因为这是一个偶函数。

所以$h'(x)\leq 0,Q.E.D.$

因此,原函数满足四边形不等式,得证。

那么直接上单调队列即可。

代码:

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
long double dp[500201];
ll L,P,n,ans[500021],a[500201],sum[500201],dl[500201],hd,ta;
inline long double fast_pow(long double a,ll b){
    long double t=1;
    while (b){
        if (b&1LL) t=t*a;
        b>>=1LL;a=a*a;
    }
    return t;
}
inline long double calc(int i,int x){
    return dp[i]+fast_pow(abs(sum[x]-sum[i]+x-i-1-L),P);
}
inline int get(int a,int b){
    if (calc(a,n)<calc(b,n)) return n+1;
    int lb=b,rb=n,ans=-1;
    while (lb<=rb){
        int mid=(lb+rb)>>1;
        if (calc(b,mid)<=calc(a,mid)) ans=mid,rb=mid-1;
        else lb=mid+1;
    }
    return ans;
}
int sta[100202],T;
char s[102002][32];
signed main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while (T--){
        cin>>n>>L>>P;
        for (int i=1;i<=n;i++){
            cin>>s[i];a[i]=strlen(s[i]);sum[i]=sum[i-1]+a[i];
            ans[i]=0;dp[i]=1e19;
        }
        hd=1,ta=1;
        for (int i=1;i<=n;i++){
            while (hd<ta&&get(dl[hd],dl[hd+1])<=i) hd++;
            ans[i]=dl[hd];dp[i]=calc(dl[hd],i);
            while (hd<ta&&get(dl[ta-1],dl[ta])>=get(dl[ta],i)) ta--;
            dl[++ta]=i;
        }
        if (dp[n]>1e18){
            puts("Too hard to arrange");
        }else{
            printf("%lld\n",(long long)dp[n]);
            int top=0;
            for (int tmp=n;tmp;tmp=ans[tmp]) sta[++top]=tmp;
            sta[++top]=0;
            for (int i=top;i>1;i--){
                for (int j=sta[i]+1;j<sta[i-1];j++){
                    printf("%s ",s[j]);
                }
                printf("%s",s[sta[i-1]]); 
                printf("\n");
            }
        }
        puts("--------------------");
    }
    return 0;
}

评论

  • star_city
    orz
作者: ww3113306 更新时间: 2018-04-26 14:52  在Ta的博客查看 举报    9  

第一次写这种二分来优化决策单调性的问题。。。。 调了好久,,,各种细节问题

显然有DP方程:

f[i]=min(f[j] + qpow(abs(sum[i] - sum[j] - L - 1)));

其中f[i]代表到了第i个句子的最小答案

qpow用于处理^p

sum为前缀和

(同时为了处理句子之间的空格问题,我们在统计前缀和的时候就默认在句子后面加一个空格,

然后在计算的时候,由于每一行只有最后一个不用加空格,直接减掉这个多加的空格即可获得正确长度)

首先我们可以打表发现是满足决策单调性的,

即决策是一段一段的

比如这种:

11122224446666

但下面这两种则不满足决策单调性:

11144442222666

11112424

同时这样的决策单调性是很特殊的,即一开始可能是这样的

11111111111111

加入2后:

11122222222222

加入4后:

11122224444444

也就是说就算最终取值是11122224446666,

在中间不断插入的过程中,也是一整段的

因此满足可二分性,

所以我们可以二分来找每个决策管理的区间(即可以转移到的区间)

但是有如下细节需要注意:

1,区间可能被完整覆盖

举个栗子,

如果当前状态是

111111111111114

现在加入一个5,那么下一个状态完全有可能是:

111111155555555

因此为了处理这样的情况,我们在二分之前先将会被完整覆盖的区间pop掉

即在插入5前弹出4,

同时这里又要注意,这个pop的处理必须在二分之前,

因为在二分过程中,我们需要一个决策来起到check的作用,而这个决策应该是当前插入的x最后应该被放入的那个区间的决策。

这样说可能不太清楚,还是举个栗子

比如当前状态:

111111112222223333

假设下一个状态是

111111112224444444

那么我们二分过程中作为判断依据的那决策就应该是2,

why?

因为观察到3号决策已经被完整的覆盖了,那么我们要对3之前的状态进行check的时候,由于3号不够优(也有可能是受到只能向后转移的限制),我们不能使用3号来check,

但是直接使用2号决策来check,然后在后面2222223333中二分也是不妥的,

因为在3333时,2号并不是最优,

所以为了应对这种情况,

我们先直接判断3333中的第一个3所对应的DP状态,如果插入的x更加优,

那么就代表这个区间是可以被完整的覆盖的,因此我们pop掉这个区间,

依次pop直到不满足条件为止,

这个时候我们就只需要在222222中二分了,于是用2号决策来check就很顺理成章了

2,新插入的x可能什么区间都覆盖不了,

也就是说新插入的x可能并不能更新状态,于是我们在二分前做一次特判,

判断当前区间的最后一个是否可以被覆盖,

如果不能,那么这个x无法更新状态,

所以直接continue

---------------以上为计算答案过程--------------

----------------以下为输出部分----------------

因为要输出方案,因此我们在转移时用last数组来记录i是从哪个决策转移而来

又因为不能打乱顺序,所以我们用Next数组来反向记录last数组

比如last中记录的可能是

0 <--- 2 <--- 4

即4由2转移而来,2由转移0而来

那么我们Next数组中记录的就是

0 ---> 2 ---> 4

所以我们从1开始输出,

每当我们到达Next[now]时就输出换行

即输出

1 2

3 4

其实也就是相当于存下了每一行是由哪一句话结尾的,

然后依次输出

最后注意ans可能很大,而且要与1e18比较,所以long long 不够用。

要用 long double

下面是代码(中间有调试输出)

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 100100
#define LL long long
#define LD long double
#define ACway 101000
#define inf 1000000000000000000LL
int t,L,p,n;
int s[AC],last[AC],l[AC],r[AC];//对应决策的管理区间
int q[AC],head,tail;//存下当前是哪个决策
int Next[AC];//对last进行相反操作,以便输出
LD f[AC];
LL sum[AC];
char ss[ACway][45];
//bool flag;
/*为什么我感觉就是一个普通DP+决策单调性 ---> 二分,,,,这个不比斜率优化容易理解么?*/
inline LD qpow(LD x)//error!!!x也要用LD!!!
{
    LD ans=1;
//  printf("x : %lld\n",(LL)(x + 0.5));
    int have=p;
    while(have)
    {
        if(have & 1) ans*=x;
        x*=x;
        have>>=1;
    //  if(ans > inf || x > inf) flag=true; 
    }
//  printf("ans : %lld\n",(LL)(ans + 0.5));
    return ans;
}

inline void pre()
{
    scanf("%d%d%d",&n,&L,&p);
    for(R i=1;i<=n;i++)
    {
        scanf("%s",ss[i]+1);
        s[i]=strlen(ss[i]+1) + 1;//加上后面的空格
        sum[i]=sum[i-1] + s[i];//求出前缀和
    }   
}

inline LD count(int x,int j)//j --- > x
{
    return f[j] + qpow(abs(sum[x] - sum[j] - L - 1));
}

void half(int x)//二分查找
{
    int now=q[tail],ll=l[now],rr=n,mid;//因为可能可以覆盖多个区间
    while(ll < rr)
    {
        mid=(ll + rr) >> 1;
        if(count(mid,x) < count(mid,now)) rr=mid;//如果更优就往左缩短
        else ll=mid + 1;//不然就向右寻找
    }
//  while(l[q[tail]] >= ll) --tail;//去掉整个都被包含的区间
    r[q[tail]]=ll-1;
    q[++tail]=x,l[x]=ll,r[x]=n;
    /*for(R i=head;i<=tail;i++)
    {
        for(R j=l[q[i]];j<=r[q[i]];j++)
            printf("%d",q[i]);
    }
    cout << endl;*/
}

inline void getans()
{
    head=1,tail=1;
    q[1]=0,l[0]=1,r[0]=n;
    for(R i=1;i<=n;i++)
    {
        while(r[q[head]] < i) ++head;//如果当前队首已经取不到了
        int now=q[head];
        //f[i]=f[now] + qpow(abs(sum[i] - sum[now] - L - 1));
        f[i]=count(i,now);//error ??? 用函数的话会爆了会自动转换为inf?
        //error!!!是后者转移到前者,所以是now ---> i,要填count(i,now),而不是count(now,i);
    //  printf("???%d\n",now);
        last[i]=now;
        if(count(n,q[tail]) < count(n,i)) continue;//如果最后一个都不够优,那就不二分了
        while(count(l[q[tail]],q[tail]) > count(l[q[tail]],i)) --tail;//如果当前可以覆盖前面的整个区间
        half(i);//注意上面的while要在调用half之前修改,这样取到的now才是正确的
    }
}

inline void write()
{
    //if(f[n] > inf || flag) puts("Too hard to arrange");
    if(f[n] > inf) puts("Too hard to arrange");
    else
    {
        printf("%lld\n",(LL)(f[n] + 0.5));//注意精度误差
        for(R i=n ; i ; i=last[i])  Next[last[i]]=i;
        int now=0;
        for(R i=1;i<=n;i++)
        {
            now=Next[now];//now先跳了吧
            int be=now;//先只到这行结尾,因为for还要加的
            for(R j=i; j < be ;j++) printf("%s ",ss[j] + 1);
            printf("%s\n",ss[be] + 1);
            i=be;//最后再赋i,因为for中还要用到当前i
        }
    }
    puts("--------------------");
}

inline void check()
{
    for(R i=1;i<=n;i++)
    {
        if(r[i] > l[i]) 
            for(R j=l[i];j<=r[i];j++) printf("%d",i);
    }
    printf("\n");
    for(R i=1;i<=n;i++) printf("!!!%lld\n",(LL)(f[i] + 0.5));
    cout << endl << endl;
}

inline void work()
{
    while(t--)
    {
        //flag=false;
        pre();
        getans();
    //  check();
        write();
    }
}

int main()
{
    freopen("in.in","r",stdin);
    scanf("%d",&t);
    work();
    fclose(stdin);
    return 0;
}

评论

  • 阿澈_
    请问dalao为什么每次队首比了之后要pp[q[h]].l++; 啊qwqqq
  • ly0216
    您的快速幂是o(n)???
  • ly0216
    太真实了吧
  • ecnerwaIa
    这个也能叫快速幂我醉了
  • cplusplus 
    真实
  • 辰星凌
    瞪眼是个好办法,学到了
  • Aehnuwx
    你家快速幂 O(n) 啊
  • Imakf
    你家快速幂 O(n) 啊
  • 森岛帆高
    你家快速幂 O(n) 啊
  • zi小眼聚光
    你家快速幂 O(n) 啊
作者: chaojidouding 更新时间: 2018-04-02 14:15  在Ta的博客查看 举报    8  

没拿到一血很不开心,那就拿个题解的一血吧

首先这个题朴素的dp不难,dp[i] 表示 前i个句子组成的文章组成的不协调值的最小值,w[i]是句子长度的前缀和(每个句子加上一个空格),转移是:

dp[i] = dp[j]+abs(w[j]-w[i-1]-l-1)^n;

考虑如何优化

可以发现,这个转移具有决策单调性(打表或者瞪眼法)

什么是决策单调性(大家可以百度:浅析1D1D动态规划的优化)

一开始对于1-n状态最优决策是

000000000000000000000000

加入1状态以后,最优决策可能就变成了

000001111111111111111111

然后加入2

000001111111112222222222

所以我们可以维护一个单调队列,每个点记录的是该状态(0,1,2)是最优决策的区间,每次加数的时候,先判断与该状态的左端点哪个更优,如果该状态更有,就pop掉(把队列里的该点全部抛弃),否则在该点对应的区间里二分查找分界点,把位于分界点右边的换成新的决策。

本题要输出方案,用一个g[i]记录转移到该状态的决策

这样就ok了

注意:

1、本题数据要小于1e18,我们应该用long double我们不能if f[i]>1e18 then f[i]=1e18,原因是(1)中间的可能会超过1e18,而结果不一定会(2)比较决策哪个优时,同时都是1e18,无法比较哪个更优,其实如果都用long double是能比较出来的

2、输出方案时每一长句话之后不要加空格,否则会错。

附上丑陋的代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
long double f[101010];
int g[101010],nxt[101010],q[101010],w[101010];
int p,l;
char a[101010][35];
struct Node
{
    int l,r;
}pp[101010];
long double ksm(int w,int x)
{
    long double ans=1;
    int i;
    for(i=1;i<=x;i++)
        ans*=w;
    return ans;
}
long double jisuan(int x,int i)
{
    long double ans;
    ans=f[x]+ksm(abs(w[i]-w[x]-1-l),p);
    return ans;
}
int main()
{
    int T,h,t,i,tmp,len,n,right,left,mid;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        memset(nxt,0,sizeof(nxt));
        memset(a,0,sizeof(a));
        memset(w,0,sizeof(w));
        memset(q,0,sizeof(q));
        memset(pp,0,sizeof(pp));
        scanf("%d%d%d",&n,&l,&p);
        w[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s",a[i]+1);
            len=strlen(a[i]+1);
            w[i]=w[i-1]+len+1;
        }
        h=0,t=1,q[h]=0;
        pp[0].l=1,pp[0].r=n;
        for(i=1;i<=n;i++)
        {
            while(h<t-1&&i>pp[q[h]].r)//队首比较 
                h++;
            f[i]=f[q[h]]+ksm(abs(w[i]-w[q[h]]-1-l),p);
            pp[q[h]].l++;
            g[i]=q[h];
            while(h<t-1&&jisuan(q[t-1],pp[q[t-1]].l)>jisuan(i,pp[q[t-1]].l))//队尾比较 
            {
                t--;
                pp[q[t]].l=0;
                pp[q[t]].r=0;
                q[t]=0;
            }
            left=pp[q[t-1]].l,right=pp[q[t-1]].r;//二分查找 
            while(left<=right)
            {
                mid=(left+right)/2;
                if(jisuan(i,mid)<=jisuan(q[t-1],mid))
                    right=mid-1;
                else
                    left=mid+1;
            }
            if(left<=n)
            {
                pp[q[t-1]].r=left-1;
                q[t++]=i;
                pp[i].l=left;
                pp[i].r=n;
            }
        }
        if(f[n]>1000000000000000000)
            printf("Too hard to arrange\n");
        else
        {
            printf("%lld\n",(long long)f[n]);
            tmp=n;
            while(tmp!=0)
            {
              nxt[g[tmp]]=tmp;
              tmp=g[tmp];
            }
            while(tmp!=n)
            {

                for(i=tmp+1;i<=nxt[tmp];i++)
                {
                    printf("%s",a[i]+1);
                    if(i!=nxt[tmp])
                        printf(" ");
                }
                printf("\n");
                tmp=nxt[tmp];
            }
        }
        printf("--------------------\n");
    }
    return 0;
}

评论

  • 还没有评论
作者: Utsuji_risshū 更新时间: 2019-03-20 23:18  在Ta的博客查看 举报    3  

n个数划分若干段,给定$L$,$p$,每段代价为$|sum_i-sum_j-1-L|^p$,求总代价最小。

正常的dp决策单调性优化题目。$f[i]$表示最小代价。然后有个正常的dp方程。

$f[i]=min \{ f[j]+|sum_i-sum_j-1-L|^p \} $

然后观察发现带高次项,不好斜率优化或单调队列,考虑有没有决策单调性。本来是可以打表证明的,然后拍一下。题解没人证单调性,于是我来瞎证一波,有错别怪我。

证明:

已知$f[j]+|sum_i-sum_j-1-L|^p < f[j']+|sum_i-sum_{j'}-1-L|^p$

要证$f[j]+|sum_i-sum_j-L|^p < f[j']+|sum_i-sum_{j'}-L|^p$ $(j'<j)$(就是$i$加了$1$)

即证 $|sum_i-sum_{j'}-1-L|^p+|sum_i-sum_j-L|^p < |sum_i-sum_j-1-L|^p+|sum_i-sum_{j'}-L|^p$

即$|sum_i-sum_{j'}-1-L|^p-|sum_i-sum_{j'}-L|^p < |sum_i-sum_j-1-L|^p-|sum_i-sum_j-L|^p$

然后把其看成关于j的函数,或者就把$S_i-S_j-L$看成$x$简便一些,$j$增大,$S_j$增大,$x$总的减小。下面看单调性。可能证的不太严谨,有问题还望指教。

$f(x)=|x-1|^p-|x|^p$ (p为大于2正整数)

①$p$为偶数,则$f(x)=(x-1)^p-x^p$

$f'(x)=p(x-1)^{p-1}-px^{p-1}$

$x>=1$时显然小于$0$,此段单调减

$0<=x<1$时$p(x-1)^{p-1}<px^{p-1}$即$p(x-1)^{p-1}-px^{p-1}<0$,此段单调减

$x<0$时也有上述关系。

又因为$x∈R$内函数值是连续(就是几个转折点值在左右边两个范围内算出来的f都一样的)的,所以整个是一直单调减的。

②$p$为奇数,$p-1$为偶,则

$x>=1$时$f'(x)=p(x-1)^{p-1}-px^{p-1}<0$单调减

$0<=x<1$时$f(x)=(1-x)^p-x^p$,则$f'(x)=-p(x-1)^{p-1}-px^{p-1}<0$因为偶数次方必定大于0嘛

$x<0$时$f(x)=(1-x)^p+x^p$ ,$f'(x)=-p(x-1)^{p-1}+px^{p-1}$

$∵x-1<x<0$

$∴(x-1)^{p-1}>x^{p-1}$

$∴f'(x)=-p(x-1)^{p-1}+px^{p-1}<0$

$综上,p为奇或偶都有导数小于0,f随x单调减,j增大,S_j增大,x减小,f必然增大,则原不等式得证。$

$所以满足决策单调性。$

$证毕。$

好像有漏洞?算了不管了。希望各位能指出或完善证明,因为我其实根本就不会求导。而且我的数学差的要死,全班倒数。

然后随便套套决策单调性模板就行啦,这个可以去看以及膜上下楼的比我强了几百万倍的julao。

注意一下要用long double范围大,不然long long会爆。注意不用刻意考虑和判断会不会爆,正常用long double虽然牺牲精度但毕竟还是总体大于$10^{18}$的。

#include<bits/stdc++.h>
#define dbg(x) cerr<<#x<<"="<<x<<endl
using namespace std;
typedef long double ll;
typedef double db;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
inline ll fpow(ll x,int p){ll ret=1;for(;p;p>>=1,x=x*x)if(p&1)ret=ret*x;return ret;}
inline int Abs(int x){return x>0?x:-x;}
const int N=100000+7;ll INF=1e18;
struct thxORZ{
    int l,r,pos;
    thxORZ(int l0=0,int r0=0,int pos0=0):l(l0),r(r0),pos(pos0){}
}q[N];
char s[N][32];
ll f[N],lim;
int sum[N],pre[N];
int T,L,p,n,l,r;
inline ll calc(int j,int i){return f[j]+fpow(Abs(sum[i]-sum[j]-1-L),p);}
inline int find_pos(int L,int R,int j,int i){
    int mid;
    while(L<R){
        mid=L+R>>1;
        if(calc(j,mid)>=calc(i,mid))R=mid;
        else L=mid+1;
    }
    return R;
}
inline void dp(){
    q[l=r=1]=thxORZ(1,n,0);
    for(register int i=1;i<=n;++i){
        f[i]=calc(q[l].pos,i);pre[i]=q[l].pos;//dbg(i),dbg(f[i]),dbg(sum[i]);
        if(i==q[l].r)++l;else ++q[l].l;
        if(f[i]>INF)continue;//小优化:当前状态如果已经无效就不要更新决策表了。
        while(l<=r&&calc(q[r].pos,q[r].l)>=calc(i,q[r].l))--r;
        if(r<l)q[r=l]=thxORZ(i+1,n,i);
        else{
            int k;if(calc(q[r].pos,q[r].r)<=calc(i,q[r].r))k=q[r].r+1;
            else k=find_pos(q[r].l,q[r].r,q[r].pos,i);//dbg(i),dbg(k);
            if(k<=n)q[r].r=k-1,q[++r]=thxORZ(k,n,i);
        }
    }
}
inline void print(int x,int y){
    if(x)print(pre[x],x);
    for(register int i=x+1;i<=y;++i)printf("%s",s[i]),i==y?putchar('\n'):putchar(' ');
}

int main(){//freopen("test.in","r",stdin);freopen("tmp.out","w",stdout);
    read(T);while(T--){
        read(n),read(L),read(p);lim=(ll)ceil(pow(1e18,1.0/(db)p));
        for(register int i=1;i<=n;++i)scanf("%s",s[i]),sum[i]=sum[i-1]+strlen(s[i])+1;
        dp();if(f[n]>INF)printf("Too hard to arrange\n");
        else printf("%lld\n",(long long)f[n]),print(pre[n],n);
        printf("--------------------\n");
    }
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。