正文

bzoj4899--记忆的轮廓

ihopenot  ihopenot  2022-09-02  191

关键词：

Description

通往贤者之塔的路上，有许多的危机。

我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，

在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正

确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。

为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档

位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者

之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走

到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假

如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点

。初始昴位于1，当昴走到正确节点n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多

少？

Input

第一行一个正整数T表示数据组数。

接下来每组数据，首先读入三个正整数n,m,p。

接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边）

用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。

数据保证j是k的父亲。

50<=p<=n<=700，m<=1500，T<=5。

数据保证每个正确节点均有至少2个儿子，至多3个儿子。

Output

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

--------------------------------------此后一千里-------------------------------------------------

题解：

首先我们设v[i][j]表示前一个存档点为 i ，走到 j 的期望步数。这个可以递推求得。

然后最优解就可以表示为v[1][a1]+v[a1][a2]+...+v[ap][n]

所以最优解可以dp得到。直接dp是n^3的，可能跑不过，观察发现由于题目性质，v[i][j]至少是v[i][j-1]的两倍，

而p大于等于50，所以v[i][i+16]及之后的值都过大，所以我们只用管前16个就可以了。

代码：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define LL long long
using namespace std;

#define int int
inline int Max(int a,int b) {return a>b?a:b;}
inline int Min(int a,int b) {return a<b?a:b;}
inline int Sqr(int a) {return a*a;}
inline int Abs(int a) {return a>0?a:-a;}
#undef int

#define MAXN 705

struct Edge{
    int to,next;
}e[MAXN*5];int head[1505],cnt;
inline void Insert(int a,int b) {
    e[++cnt].next=head[a];head[a]=cnt;e[cnt].to=b;
}

double v[MAXN][MAXN],r[1505],E[1505],dp[MAXN][MAXN];
int n,m,p,T;

void Dp(int v) {
    E[v]=0;
    for(int i=head[v];i;i=e[i].next) {
        Dp(e[i].to);E[v]+=E[e[i].to];
    }
    if(r[v]) E[v]/=r[v];
    E[v]++;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        memset(head,0,sizeof(head));cnt=0;
        memset(r,0,sizeof(r));
        scanf("%d%d%d",&n,&m,&p);p--;
        for(int a,b,i=n+1;i<=m;i++) {
            scanf("%d%d",&a,&b);
            Insert(a,b);r[a]++;
        }
        for(int i=1;i<n;i++) r[i]++;
        for(int i=1;i<=n;i++) {
            E[i]=0;
            for(int j=head[i];j;j=e[j].next) {
                Dp(e[j].to);E[i]+=E[e[j].to];
            }
        }
        for(int i=1;i<=n;i++) 
            for(int j=i+1;j<=n;j++) {
                if(i-j>16) break;
                v[i][j]=E[j-1]+r[j-1]+r[j-1]*v[i][j-1];
            }
        for(int i=1;i<=n;i++) for(int j=0;j<=p;j++) dp[i][j]=1e20;
        dp[n][0]=0;
        for(int i=n;i;i--) 
            for(int j=1;j<=p;j++) 
                for(int k=i+1;k<=n;k++) {
                    if(k-i>16) break;
                    dp[i][j]=min(dp[i][j],v[i][k]+dp[k][j-1]);
                }
        printf("%.4lf
",dp[1][p]);
    }
    return 0;
}

View Code

考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)

...没有调出来）最后骗了五分考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天查看详情

loj6171/bzoj4899记忆的轮廊（期望dp+优化）

题目：https://loj.ac/problem/6171分析：设dp[i][j]表示从第i个点出发（正确节点），还可以有j个存档点（在i点使用一个存档机会），走到终点n的期望步数那么a[i][k]表示i点为存档点，从i点走到k点（正确节点）的期望步数（中间没有... 查看详情

bzoj千题计划307：bzoj5248:[2018多省省队联测]一双木棋(代码片段)

...一定是阶梯状，且从上往下递减可以将轮廓线作为状态，记忆化搜索用n个数表示一个状态，第i个数表示第i行放了几个记忆的状态表示当棋盘为这个状态时，接下来再下的最有解记忆化搜索节省的是接下来再下的时间 #i 查看详情

bzoj1079--记忆化搜索

...不现实。注意到ci相等的颜色本质上是相同的，于是可以记忆化搜索。时间复杂度：O(15^5 查看详情

bzoj3810:[coci2015]stanovi(记忆化搜索)

...[u][d]表示x*y的矩阵上下左右是不是边界的最小代价。　　记忆化搜索一下横着切和竖着切。　　但是这样会被卡。。我们令x>=yl>=ru>=d可以减少很多相同的状态数，而且答案是不变的，这样常数小很多才能过#include<iost 查看详情

bzoj1417pku3156interconnect记忆化搜索

【BZOJ1417】Pku3156InterconnectDescription给出无向图G(V,E).每次操作任意加一条非自环的边(u,v),每条边的选择是等概率的.问使得G连通的期望操作次数.(|V|<=30,|E|<=1000)Input第一行两个整数N,M1<=N<=300<=M<=1000接下来M行,每行两个整... 查看详情

bzoj4428[nwerc2015]debugging调试记忆化搜索+分块

【BZOJ4428】[Nwerc2015]Debugging调试Description你看中的调试器将不会在这件事上帮助你。有代码可以通过多种方式在调试与正式发布的间隙发生不同的行为，当出现这种情况，我们可能不得不求助于更原始的调试方式。所以，你和你的... 查看详情

bzoj-1048:[haoi2007]分割矩阵(记忆化搜索)

1048:[HAOI2007]分割矩阵TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 1040 Solved: 751[Submit][Status][Discuss]Description　　将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两查看详情

bzoj1589trickortreatonthefarm（tarjan缩点，记忆化搜索）[usaco2008decgold]bzoj计划(代码片段)

整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划Weblinkhttps://hydro.ac/d/bzoj/p/1589Problem每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的nnn个牛棚里... 查看详情

bzoj1589trickortreatonthefarm（tarjan缩点，记忆化搜索）[usaco2008decgold]bzoj计划(代码片段)

bzoj.2246.[sdoi2011]迷宫探险(dp记忆化搜索概率)

题目链接求最大的存活概率，DP+记忆化。用f[s][x][y][hp]表示在s状态，(x,y)点，血量为hp时的存活概率。s是个三进制数，记录每个陷阱无害/有害/未知。转移时比较容易，主要是在陷阱未知时需要知道当前状态这个陷阱为有害/无害... 查看详情

bzoj3769spoj8549bstagaindp（记忆化搜索?）

【BZOJ3769】spoj8549BSTagainDescription求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）Input第一行一个整数T，表示数据组数。以下T行，每行2个整数n和h。Output共T行，每行一个整数表示答案... 查看详情

[bzoj1032][p1840]祖玛记忆化搜索动态规划

描述Description 某天，小x在玩一个经典小游戏——zumo。zumo游戏的规则是，给你一段长度为n的连续的彩色珠子，珠子的颜色不一定完全相同，但是，如果连续相同颜色的珠子大于等于k个，这些珠子就会消失... 查看详情

bzoj5123[lydsy12月赛]线段树的匹配树形dp+记忆化搜索

...的线段树的最大匹配数目与方案数。$nle10^{18}$题解树形dp+记忆化搜索设$f[l][r]$表示根节点为$[l,r]$的线段树，匹配选择根节点的最大匹配&方案数，$g[l][r]$表示根节点为$[l,r]$的线段树，匹配不选择根节点的最大匹配&方案数。... 查看详情

bzoj4428[nwerc2015]debugging调试数论+记忆化搜索

题目描述一个$n$行的代码出了bug，每行都可能会产生这个bug。你要通过输出调试，在其中加入printf来判断bug出现的位置。运行一次程序的时间为$r$，加入一条printf的时间为$p$，求最坏情况下调出程序的最短时间。输入输入包括一... 查看详情

bzoj1638:[usaco2007mar]cowtraffic奶牛交通记忆化搜索

震惊！记忆化搜索忘记返回map值调了半小时！边(u,v)的经过次数是：能到u的牛数*v到n的方案数。正反两次连边，dfs两次即可#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=5005,M=50005;intn,m,x[M],y[M],h[N],cnt, 查看详情

bzoj1079着色方案记忆化搜索（dp）(代码片段)

题目传送门题目大意：　　有k种颜色，每个颜色ci可以涂个格子，要求相邻格子颜色不能一样，求方案数。ci<=5,k<=15.思路：　　题目里最重要的限制条件是相邻格子颜色不能相同，也就是当前格子只和上一个格子有关，那么... 查看详情

bzoj1833:[zjoi2010]count数字计数(数位dp+记忆化搜索)(代码片段)

...佬啊！！！　　据说是数位DP裸题...emmm学吧学吧　　感觉记忆化搜索特别强：　　定义f[i][j][k]表示若前i个位置有k个j的此时的全局方案数，然后就可以记忆化搜索了（具体看代码吧）　　 &nbs 查看详情