bzoj 4899 记忆的轮廓题解（概率dp+决策单调性优化）

题目背景

四次死亡轮回后，昴终于到达了贤者之塔，当代贤者夏乌拉一见到昴就上前抱住了昴“师傅！你终于回来了！你有着和师傅一样的魔女的余香，肯定是师傅”。
众所周知，大贤者是嫉妒魔女沙提拉的老公，400年前与神龙、剑圣一起封印魔女因子暴走的莎缇拉。在魔女茶会的时候，莎缇拉也表示过对昴浓浓的爱意，昴便是被莎缇拉召唤来异世界的。
而贤者之塔中的资料与试炼，似乎都指向同一种可能性……记忆的轮廓，逐渐显形……

题目描述

通往贤者之塔的路上，有许多的危机。
我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。
我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。
莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。
当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走到一个错误叶子时，再走一步就会读档。
具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点。
初始昴位于1，当昴走到正确叶子n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多少？
输入格式

第一行一个正整数T表示数据组数。
接下来每组数据，首先读入三个正整数n,m,p。
接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边），用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。数据保证j是k的父亲。
输出格式

T行每行一个实数表示每组数据的答案。请保留四位小数。

样例输入

1
3 7 2
1 4
2 5
3 6
3 7

样例输出

9.000

数据范围及约定

50%，n=p
70%，50<=p<=n<=500
100%，50<=p<=n<=700，m<=1500，T<=5
数据保证每个除了n的正确节点均有至少2个儿子，至多3个儿子。

---------------------------------------------------------------分界线---------------------------------------------------------------

考试T2，调考前刚qj过改过，确实是一道毒瘤题好题，考试时时间不够看都没看考完试才开始做了这题。

理解题理解了一节课

做题先看数据范围，否则凉凉。

我们可以看到有50%的数据是n=p的，对于n=p的情况，我们不难分析出每个点都存档是最优解，这样情况就简单很多。

接下来我们考虑怎么转移。

设个g[i]为对于一个错误节点i还要走多少步会存档。

g[i]=1+∑g[j]/du[i]（j是i的儿子）。一遍dfs就可以处理出来g数组。

我们再处理数组sum,sum[i]=∑g[j]（j是i的错误儿子）。

设f[i]表示正确节点i走到n的期望步数，显然f[n]=0，我们倒着递推。
f[i]=1+1/d[i]*f[i+1]+1/d[i]*sigma{g[j]+f[i]}[j是i的错误儿子]
移项得f[i]=d[i]+f[i+1]+s[i]。

over，50pts到手。

接下来我们考虑把它优化到70pts。

设dp（i，j）表示存档点在i还有j次存档机会的最优解。

设a（i，j）表示存档点在i，从i走到正确节点j的最少期望步数。

首先我们可以o（n²）把a数组处理出来。

a（i，j）=a（i，j-1）+1+1/du（j-1）×∑（a（i，j）+g（k））{k是j-1的错误儿子}。

整理移项得a（i，j）=du（i，j-1）×a（i，j-1）+sum（j-1）+du（j-1）。

然后我们枚举存档点k，则dp（i，j）可以由dp（k，j-1）和a（i，k）转移。

时间复杂度O（n²p），70pts到手。

最后我们来考虑正解。其实博主并不会正解。

还是放直链吧。%%%出题人。

https://blog.csdn.net/WerKeyTom_FTD/article/details/53026266

出题人给出了三种正解。

由于第二种看起来十分好写比较优秀，博主选择了第二种。

到现在博主还是很mengbi，在这里就不给予讲解了。

如果有时间的话博主也会用其他两种方法A掉这题的。

下面是三个分数段的代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

const int N=;

using namespace std;

int first[N],nex[N],to[N],tot,vis[N],du[N];double sum[N],g[N],f[N];

void add(int a,int b){

    to[++tot]=b;nex[tot]=first[a];first[a]=tot;

}

void dfs(int x){

    g[x]=1.0;vis[x]=;

    for(int i=first[x];i;i=nex[i]){

        int y=to[i];

        dfs(y);

        g[x]+=1.0/du[x]*g[y];

    }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        memset(du,,sizeof(du));

        //memset(sum,0,sizeof(sum));

        memset(g,,sizeof(g));tot=;

        int n,m,p;

        scanf("%d%d%d",&n,&m,&p);

        for(int i=;i<=m-n;i++){

            int a,b;

            scanf("%d%d",&a,&b);

            add(a,b);

            du[a]++;

        }

        for(int i=;i<=n;i++) du[i]++;

        for(int i=n+;i<=m;i++){

            if(vis[i]) continue;

            dfs(i);

        }

        for(int i=;i<=n;i++){

            sum[i]=0.0;

            for(int j=first[i];j;j=nex[j]){

                //if(j>n&&j<=m)

                if(to[j]>n&&to[j]<=m)

                sum[i]+=g[to[j]];

            }

        }

        f[n]=0.0;

        for(int i=n-;i>=;i--){

            f[i]=f[i+]+sum[i]+du[i];

            //cout<<g[i]<<" ";

        }

        //for(int i=n+1;i<=m;i++) /*cout<<i<<" ",*/printf("%.4lf ",g[i]);

        printf("%.4lf\n",f[]);

    }

}

50pts

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

#define R register

inline int read(){

    R int aa=,bb=;char cc=getchar();

    while(cc<''||cc>'')

        {if(cc=='-')bb=-;cc=getchar();}

    while(cc<=''&&cc>='')

        {aa=aa*+cc-'';cc=getchar();}

    return aa*bb;

}

const int N=;

const int M=;

struct tree{

    int v,last;

}tr[M*];

int tot=,first[M],du[M];

void add(int x,int y){

    tr[++tot].v=y;

    tr[tot].last=first[x];

    first[x]=tot;

    du[x]++;

}

int T,n,m,p;

bool vi[M];

double g[M],sum[N],f[N][N],fg[N][N],fi[N];

void dfs(int x){

    if(vi[x]) return;

    g[x]=1.0; vi[x]=;

    for(R int i=first[x],v;i;i=tr[i].last){

        v=tr[i].v;

        dfs(v);

        g[x]+=1.0/du[x]*g[v];

    }

}

int main(){

    T=read();

    while(T--){

        memset(vi,,sizeof(vi));

        memset(du,,sizeof(du));

        memset(first,,sizeof(first));

        tot=;

        n=read();m=read();p=read();

        for(R int i=,x,y;i<=m-n;i++){

            x=read();y=read();

            add(x,y);

        }

        for(R int i=;i<=n;i++)du[i]++;

        for(R int i=n+;i<=m;i++) if(!vi[i]) dfs(i);

        for(R int i=;i<=n;i++){

            sum[i]=0.0;

            for(R int j=first[i],v;j;j=tr[j].last){

                v=tr[j].v;

                sum[i]+=1.0*g[v];

            }

        }

        if(n==p){

            fi[n]=0.0;

            for(R int i=n-;i>=;i--)

                fi[i]=(double)(du[i]+fi[i+]+sum[i]);

            printf("%.4lf\n",fi[]);

            continue;

        }

        for(R int i=;i<=n;i++){

            fg[i][i]=0.0;

            for(R int j=i+;j<=n;j++){

                fg[i][j]=fg[i][j-]*du[j-]+du[j-]+sum[j-];

            }

        }

        for(R int i=;i<=n;i++)

            for(R int j=;j<=p;j++)

                f[i][j]=0x7ffffff;

        for(R int i=;i<=p;i++)  f[n][i]=0.0;

        for(R int i=n-;i>=;i--){

            for(R int j=;j<p;j++){

                for(R int k=i+;k<=n;k++){

                    f[i][j]=min( f[k][j-]+fg[i][k], f[i][j]);

                }

            }

        }

        printf("%.4lf\n",f[][p-]);

    }

    return ;

}

70pts

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

#define R register

inline int read()

{

    R int aa=,bb=;char cc=getchar();

    while(cc<''||cc>'')

        {if(cc=='-')bb=-;cc=getchar();}

    while(cc<=''&&cc>='')

        {aa=aa*+cc-'';cc=getchar();}

    return aa*bb;

}

const int N=;

const int M=;

struct tree{

    int v,last;

}tr[M*];

int tot=,first[M],du[M];

void add(int x,int y)

{

    tr[++tot].v=y;

    tr[tot].last=first[x];

    first[x]=tot;

    du[x]++;

}

int T,n,m,p;

bool vi[M];

double g[M],sum[N],f[N][N],fg[N][N],fi[N];

void dfs(int x)

{

    if(vi[x]) return;

    g[x]=1.0; vi[x]=;

    for(R int i=first[x],v;i;i=tr[i].last){

        v=tr[i].v;

        dfs(v);

        g[x]+=1.0/du[x]*g[v];

    }

}

int main()

{

    T=read();

    while(T--){

        memset(vi,,sizeof(vi));

        memset(du,,sizeof(du));

        memset(first,,sizeof(first));

        tot=;

        n=read();m=read();p=read();

        for(R int i=,x,y;i<=m-n;i++){

            x=read();y=read();

            add(x,y);

        }

        for(R int i=;i<=n;i++)du[i]++;

        for(R int i=n+;i<=m;i++) if(!vi[i]) dfs(i);

        for(R int i=;i<=n;i++){

            sum[i]=0.0;

            for(R int j=first[i],v;j;j=tr[j].last){

                v=tr[j].v;

                sum[i]+=1.0*g[v];

            }

        }

        if(n==p){

            fi[n]=0.0;

            for(R int i=n-;i>=;i--)

                fi[i]=(double)(du[i]+fi[i+]+sum[i]);

            printf("%.4lf\n",fi[]);

            continue;

        }

        for(R int i=;i<=n;i++){

            fg[i][i]=0.0;

            for(R int j=i+;j<=n;j++){

                fg[i][j]=fg[i][j-]*du[j-]+du[j-]+sum[j-];

            }

        }

        for(R int i=;i<=n;i++)

            for(R int j=;j<=p;j++)

                f[i][j]=0x7ffffff;

        for(R int i=;i<=p;i++)  f[n][i]=0.0;

        for(R int i=n-;i>=;i--){

            for(R int j=;j<p;j++){

                int r=min(i+,n);

                for(R int k=i+;k<=r;k++){

                    f[i][j]=min( f[k][j-]+fg[i][k], f[i][j]);

                }

            }

        }

        printf("%.4lf\n",f[][p-]);

    }

    return ;

}

巴特西

bzoj 4899 记忆的轮廓题解（概率dp+决策单调性优化）

题目背景

题目描述

样例输入

样例输出

数据范围及约定

最新文章

热门文章

巴特西

bzoj 4899 记忆的轮廓 题解（概率dp+决策单调性优化）

题目背景

题目描述

样例输入

样例输出

数据范围及约定

最新文章

热门文章

bzoj 4899 记忆的轮廓题解（概率dp+决策单调性优化）