首页 > 代码库 > Bzoj4899--记忆的轮廓
Bzoj4899--记忆的轮廓
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 longusing namespace std;#define int intinline 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 705struct 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\n",dp[1][p]); } return 0;}
Bzoj4899--记忆的轮廓
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。