[HYBZ 1563/NOI2009 day1 诗人小G]决策单调优化、动态规划**

题目地址:http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1563

【算法分析】

容易得到方程f[i]=min(f[j]+|sum[j]-sum[i]+j-i-1-L|^P)

令w(j,i)=|sum[j]-sum[i]+j-i-1-L|^P

则f[i]=min(f[j]+w[j,i])

这是经典的1D/1D模式的DP方程。

首先我们来证明一个性质:

命题1:对于i

证明:

令g(x)=|x|^P

1、P为偶数,对其求导得g(x)’=P*x^(P-1),是单调递增的。

2、P为奇数,对其求导得g(x)’=P*x^(P-1)*(x/|x|),容易发现,同样是单调递增的。

由于导函数单调递增,而导函数的定积分又对应于g(x)的变化量。

若a

而对于我们的w函数,随着i的增加,w[j,i]的增量是相同的,

所以相当于把g(x)不断向左平移

由于f[i]又是固定的常数,所以命题1得证。

下面再证明另外一个性质:

命题2:方程满足决策单调性。

方程满足凸四边形不等式<=>方程满足决策单调性

w[i,j]满足凸四边形不等式当且仅当:

固定j以后,将w[i,j+1]-w[i,j]表示为i的函数,该函数的导数恒<=0。

(这个结论位于《算法艺术与信息学竞赛》的152页,定理3下面)

令g(i)=w[i,j+1]-w[i,j],即g(i)=sum[j+1]-sum[i]+1-(sum[j]-sum[i])=a[j+1]+1。

所以g(i)为常数函数,g'(i)=0。

满足条件。

所以,综上所述,命题2得证。

于是我们就可以开一个双端队列维护决策序列了。

这个序列每一个域包含3个元素,两个是表示该点造成最优决策的区间,第3个是表示这个点是哪个。

然后我们维护这个队列即可得到最优解。

维护方法:

头部:顺次下去,如果i超过区间尾就到下一个决策区间。

尾部:每次把新弄好的i试图插进去,从后面开始,如果它负责的区域都没有i好,那么就把它删掉。由于命题1,我们只需要判断开头的结点就可以了。

当然,如果它负责的区域包含的<=i的点,那么就不可能删掉它了,因为i这个点不能完全替代它。

所以最后不可能把队列的元素都删掉,然后对队尾元素进行二分,看什么时候i这个点能够超越它。(这依赖于命题1的性质)

然后修改区间就可以了。

【其它】1A

【CODE】

#include #include #include #include using namespace std;
const int N=101111;
const long long INF=(long long)(1000000000)*(long long)(1000000000);
char S[N][33];
struct Queue_Type{int l,r,p;}Q[N];
int n,P,L,head,tail;
int a[N],sum[N],fa[N],v[N];
long long f[N];

double w(int j,int i){
    int x=sum[i]-sum[j]-1-L;
    if (x<0) x=-x;
    double ans=1;
    for (int i=1;i<=P;i++) ans*=x;
    ans+=f[j];
    return ans;
}   

long long lw(int j,int i){
    int x=sum[i]-sum[j]-1-L;
    if (x<0) x=-x;
    long long ans=1;
    for (int i=1;i<=P;i++) ans*=x;
    ans+=f[j];
    return ans;
}

void input(){
    cin >> n >> L >> P;
    sum[0]=0;
    for (int i=1;i<=n;i++){
        scanf("%s",S[i]+1);
        a[i]=strlen(S[i]+1);
        sum[i]=sum[i-1]+a[i]+1;
    }   
    sum[n+1]=sum[n]+1;
}   

void insert(int i){
    if (i==n) return;
    while (Q[tail].l>i && w(Q[tail].p,Q[tail].l)>=w(i,Q[tail].l)){
        tail–;
        Q[tail].r=n;
    }   
    int l=i+1,r=n,mid;
    if (Q[tail].l>i+1) l=Q[tail].l;
    while (l        mid=(l+r)/2;
        if (w(Q[tail].p,mid)>=w(i,mid)) r=mid;
                                   else l=mid+1;
    }
    if (w(Q[tail].p,l)    Q[++tail].p=i;
    Q[tail].l=l;
    Q[tail].r=n;
    Q[tail-1].r=l-1;
}   

void work(){
    memset(Q,0,sizeof(Q));
    head=0; tail=0; Q[0].l=1; Q[0].r=n; Q[0].p=0; f[0]=0;
    for (int i=1;i<=n;i++){
        while (i>Q[head].r) head++;
        if (w(Q[head].p,i)>INF+10 || lw(Q[head].p,i)>INF) f[i]=-1;
        else{   
          f[i]=lw(Q[head].p,i);
          fa[i]=Q[head].p;
          insert(i);
        }   
    }   
}   

void output(){
    if (f[n]==-1){
        printf("Too hard to arrangen");
        return;
    }   
    cout << f[n] << endl;
/*    memset(v,0,sizeof(v));
    for (int i=n;i;i=fa[i]) v[i]=1;
    for (int i=1;i<=n;i++){
        printf("%s",S[i]+1);
        if (v[i]) printf("n");
             else printf(" ");
    }    */
}   

int main(){
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
        input();
        work();
        output();
        printf("——————–n");
    }   
}

加入对话

11条评论

  1. 回复卡通BlueEye:oh,是的。。。重新看了一遍黑书。。。又有点糊涂了它上面说:如果w同时满足凸四边形不等式和区间单调关系,那么f也满足四边形不等式。

  2. 回复卡通BlueEye:而byvoid的证明中说,这个方程满足决策单调当且仅当w符合四边形不等式。这到底是怎么搞@_@,好像这个不需要区间关系单调啊。求lcc大牛的理解?

  3. 回复edward_mj:区间关系单调是要f[i][j] = min{f[i’][j’] + w[i][j]}这种方程需要满足的。1D/1D优化只需要凸完全单调性就可以了。而四边形不等式是比凸完全单调还要强的结论。可以推出凸完全单调 – -话说您留个QQ给我吧。。。orz。

留下评论

回复 卡通BlueEye 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注