关键词：
题目背景
四次死亡轮回后，昴终于到达了贤者之塔，当代贤者夏乌拉一见到昴就上前抱住了昴“师傅！你终于回来了！你有着和师傅一样的魔女的余香，肯定是师傅”。
众所周知，大贤者是嫉妒魔女沙提拉的老公，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]*sigmag[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（n2）把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（n2p），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=3005; 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]=1; 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,0,sizeof(du)); //memset(sum,0,sizeof(sum)); memset(g,0,sizeof(g));tot=0; int n,m,p; scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=m-n;i++) int a,b; scanf("%d%d",&a,&b); add(a,b); du[a]++; for(int i=1;i<=n;i++) du[i]++; for(int i=n+1;i<=m;i++) if(vis[i]) continue; dfs(i); for(int i=1;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-1;i>=1;i--) f[i]=f[i+1]+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[1]);
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; #define R register inline int read() R int aa=0,bb=1;char cc=getchar(); while(cc<‘0‘||cc>‘9‘) if(cc==‘-‘)bb=-1;cc=getchar(); while(cc<=‘9‘&&cc>=‘0‘) aa=aa*10+cc-‘0‘;cc=getchar(); return aa*bb; const int N=703; const int M=1503; struct tree int v,last; tr[M*2]; int tot=0,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]=1; 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,0,sizeof(vi)); memset(du,0,sizeof(du)); memset(first,0,sizeof(first)); tot=0; n=read();m=read();p=read(); for(R int i=1,x,y;i<=m-n;i++) x=read();y=read(); add(x,y); for(R int i=1;i<=n;i++)du[i]++; for(R int i=n+1;i<=m;i++) if(!vi[i]) dfs(i); for(R int i=1;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-1;i>=1;i--) fi[i]=(double)(du[i]+fi[i+1]+sum[i]); printf("%.4lf\n",fi[1]); continue; for(R int i=1;i<=n;i++) fg[i][i]=0.0; for(R int j=i+1;j<=n;j++) fg[i][j]=fg[i][j-1]*du[j-1]+du[j-1]+sum[j-1]; for(R int i=1;i<=n;i++) for(R int j=0;j<=p;j++) f[i][j]=0x7ffffff; for(R int i=0;i<=p;i++) f[n][i]=0.0; for(R int i=n-1;i>=1;i--) for(R int j=1;j<p;j++) for(R int k=i+1;k<=n;k++) f[i][j]=min( f[k][j-1]+fg[i][k], f[i][j]); printf("%.4lf\n",f[1][p-1]); return 0;
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; #define R register inline int read() R int aa=0,bb=1;char cc=getchar(); while(cc<‘0‘||cc>‘9‘) if(cc==‘-‘)bb=-1;cc=getchar(); while(cc<=‘9‘&&cc>=‘0‘) aa=aa*10+cc-‘0‘;cc=getchar(); return aa*bb; const int N=703; const int M=1503; struct tree int v,last; tr[M*2]; int tot=0,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]=1; 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,0,sizeof(vi)); memset(du,0,sizeof(du)); memset(first,0,sizeof(first)); tot=0; n=read();m=read();p=read(); for(R int i=1,x,y;i<=m-n;i++) x=read();y=read(); add(x,y); for(R int i=1;i<=n;i++)du[i]++; for(R int i=n+1;i<=m;i++) if(!vi[i]) dfs(i); for(R int i=1;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-1;i>=1;i--) fi[i]=(double)(du[i]+fi[i+1]+sum[i]); printf("%.4lf\n",fi[1]); continue; for(R int i=1;i<=n;i++) fg[i][i]=0.0; for(R int j=i+1;j<=n;j++) fg[i][j]=fg[i][j-1]*du[j-1]+du[j-1]+sum[j-1]; for(R int i=1;i<=n;i++) for(R int j=0;j<=p;j++) f[i][j]=0x7ffffff; for(R int i=0;i<=p;i++) f[n][i]=0.0; for(R int i=n-1;i>=1;i--) for(R int j=1;j<p;j++) int r=min(i+40,n); for(R int k=i+1;k<=r;k++) f[i][j]=min( f[k][j-1]+fg[i][k], f[i][j]); printf("%.4lf\n",f[1][p-1]); return 0;
决策单调性优化dp专题练习
...调性优化A:Lawrence题解传送门B:LightningConductor题解传送门C:记忆的轮廓题解传送门D:区间题解传送门E:Post加强版题解以及拓展三、四边形不等式石子合并。。。 查看详情
[bzoj4709][jsoi2011]柠檬决策单调性优化dp
...ydsy.com/JudgeOnline/problem.php?id=4709我好弱啊QAQ，网上dalao们的题解根本看不懂啊，折腾了几个小时，有一点明白了。首先要把朴素dp方程退出来。①题目中说每次从序列的左右选一端取，但是如果你真的照着题目说的这样做我也不知... 查看详情
loj6171/bzoj4899记忆的轮廊（期望dp+优化）
题目：https://loj.ac/problem/6171分析：设dp[i][j]表示从第i个点出发（正确节点），还可以有j个存档点（在i点使用一个存档机会），走到终点n的期望步数那么a[i][k]表示i点为存档点，从i点走到k点（正确节点）的期望步数（中间没有... 查看详情
bzoj2246[sdoi2011]迷宫探险记忆化搜索dp+概率(代码片段)
题目输入格式输出格式仅包含一个数字，表示在执行最优策略时，人物活着走出迷宫的概率。四舍五入保留3位小数。输入样例4332.$.A#BA#C@@@1433733585952522357输出样例0.858提示题解毒瘤dp题我们设\(f[x][y][s][h]\)表示从点\((x,y)\)出发，所... 查看详情
bzoj2216[poi2011]lightningconductor决策单调性+dp(代码片段)
题面题目传送门解法决策单调性比较经典的题吧题目就是要对于每一个(i)求(f_i=max(a_j-a_i+sqrt|i-j|)))可以发现，(sqrtn)的增长速度比较慢，所以满足决策单调性决策单调性是指，如果决策(j)对于(i)已经不是最优的了，那么在后面也一... 查看详情
bzoj4518:[sdoi2016]征途（dp+决策单调性分治优化）
...gma(si^2)最小，那就变成了求最小平方和的最小值，经典的决策单调性，用分治优化即可。 斜率优化忘得差不多就不写了#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#i 查看详情
bzoj.2246.[sdoi2011]迷宫探险(dp记忆化搜索概率)
题目链接求最大的存活概率，DP+记忆化。用f[s][x][y][hp]表示在s状态，(x,y)点，血量为hp时的存活概率。s是个三进制数，记录每个陷阱无害/有害/未知。转移时比较容易，主要是在陷阱未知时需要知道当前状态这个陷阱为有害/无害... 查看详情
bzoj2687
整体二分+决策单调性这个方法已经忘了...决策单调性是指dp[i]由dp[1]->dp[i-1]更新,那么当dp[j]比dp[k]优且j>k时，对于i->nj都比k优通过这个性质我们可以把dp优化到nlogn具体做法是整体二分solve(l,r,L,R)表示当前对于l->r的dp决策... 查看详情
考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)
...没有调出来）最后骗了五分 考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天 查看详情
题解bzoj3036:绿豆蛙的归宿（期望dp）(代码片段)
题面戳我Solution反向建图跑拓扑排序，顺便处理(dp)假设某条边是(uightarrowv(dis))，那么转移方程就是(dp[v]+=(dp[u]+dis)/in[v])根据题意我们可以知道，每个点选择道路的概率是一样的，所以只能这么做。（重点在看什么的概率相同（雾... 查看详情
bzoj2216:[poi2011]lightningconductor（分治决策单调性优化）
每个pi要求 这个只需要正反DP（？）一次就行了，可以发现这个是有决策单调性的，用分治优化#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<algorithm>usingnamespace 查看详情
bzoj2442[usaco2011open]修剪草坪：单调队列优化dp
...连续的数不能超过k个。 问你最大的选数之和。 题解： 表示状态： dp[i]表示考虑了第i个数的最大之和。 找出答案： ans=dp[n] 将所有的数都考虑过了 如何 查看详情
bzoj1233干草堆-单调队列优化dp(代码片段)
...并且每层的宽度不大于它的下面一层， 求最多叠几层题解： zkw神牛证明了：底边最短，层数最高 证明：传送门 接下来我们就可以根据这个结论进行dp。前缀和sum，以及F[i]... 查看详情
bzoj2246迷宫探险（概率+dp）(代码片段)
...为S，在坐标\((i,j)\)，血量为h时的答案然后就可以DP了，记忆化搜索Code#include<cstdio>#include<algorithm>#d 查看详情
bzoj3566:[shoi2014]概率充电器
...条边有导电概率pi%，问期望有多少结点处于充电状态？【题解】引用自：【BZOJ3566】【SHOI2014】概率充电器树形DP概率DP by 空灰冰魂最大的难点在于计算每个点充电期望时，两个节点各自的期望都会影响对方的期望。所以... 查看详情
cf868f.yetanotherminimizationproblem(决策单调性分治dp)(代码片段)
...的数的对数，最小化代价总和。(n<=10^5，m<=20)Sol看完题解之后的感受：首先列出裸的dp方程，(f[i][j])表示前(i)个位置，切了(j)次，转移的时候枚举上一次且在了哪儿(f[i][j]=max(f[k][j-1]+w(k,i)))(w(k,i)) 查看详情
决策单调性优化dp(代码片段)
决策单调性：对于一些dp方程，经过一系列的猜想和证明，可以得出，所有取的最优解的转移点（即决策点）位置是单调递增的。即：假设f[i]=min(f[j]+b[j])(j<i)并且，对于任意f[i]的决策点g[i]，总有f[i+1]的决策点g[i+1]>=g[i](或者&... 查看详情
codeforces148dbagofmice：概率dp记忆化搜索
题目链接：http://codeforces.com/problemset/problem/148/D题意： 一个袋子中有w只白老鼠，b只黑老鼠。 公主和龙轮流从袋子里随机抓一只老鼠出来，不放回，公主先拿。 公主每次抓一只出来。龙每次在抓一只出来之后，会随机... 查看详情