首页 > 代码库 > BZOJ 1563 诗人小G（四边形优化）

BZOJ 1563 诗人小G（四边形优化）

2024-07-08 23:51:45   222人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1563

题意：

思路：设s[i]表示前i个句子的长度和，那么有转移方程：


有大牛证明这个满足四边形不等式，证明应该比较复杂。在《1D/1D动态规划优化初步》这篇文章中，作者说实战中可以直接打表看看是不是满足，感觉还是比较实用的。不管那么多了，现在我们知道了满足四边形不等式，也就是满足决策点单调。比如f[i]是用j更新的，那么i之后的点不可能用j之前的点更新，这就是决策单调性。那么我们怎么维护这个呢？

 

struct node{    int L,R,id;    node(){}    node(int _L,int _R,int _id)    {        L=_L;        R=_R;        id=_id;    }};node Q[N];int s[N],n,L,P;long double F[N];long double C(int i,int j){    return F[i]+pow(fabs(s[j]-s[i]+j-i-1-L),P);}void DP(){    int H=0,T=0;    Q[0]=node(1,n,0);    int i,L,R,mid,ans;    FOR1(i,n)    {        while(i>Q[H].R) H++;        F[i]=C(Q[H].id,i);        if(C(i,n)>C(Q[T].id,n)) continue;        while(i<Q[T].L&&C(i,Q[T].L)<C(Q[T].id,Q[T].L)) T--;                L=max(Q[T].L,i+1);        R=Q[T].R;        ans=min(n,Q[T].R+1);        while(L<=R)        {            mid=(L+R)>>1;            if(C(i,mid)<C(Q[T].id,mid)) R=mid-1,ans=mid;            else L=mid+1;        }        Q[T].R=ans-1;        Q[++T]=node(ans,n,i);    }    if(F[n]>dinf)    {        puts("Too hard to arrange");    }    else printf("%lld\n",(i64)F[n]);    puts("--------------------");}int get(){    int L=0;    char c=getchar();    while(c!=‘\n‘)    {        L++;        c=getchar();    }    return L;}int main(){    rush()    {        RD(n,L,P);        char c=getchar();        while(c!=‘\n‘) c=getchar();        int i;        FOR1(i,n) s[i]=get()+s[i-1];        DP();    }}

 

 


联系
我们