出题大佬题解：https://blog.csdn.net/WerKeyTom_FTD/article/details/53026266
期望DP题，感觉很有意思（第一次接触到50%，70%类似题解，步步优化的感觉稍爽）。
%出题人...
50%算法：数据中点明有50%数据n==p，此时不用考虑存档点设在哪里（所有的正确节点），那就与p无瓜，思路较简单。
设f[i]表示i到n的期望步数（f[n]==0）。关键：考虑错误节点的贡献：
在走到正确节点时等概率选择儿子，选择正确儿子贡献很显然：(f[i+1]+1)*1/son[i]
那对于正确节点的错误儿子就得知到它期望走到读档（回到正确节点）的步数，错误节点只有错误儿子所以比较简单
：g[i]=1/son[i]*sigma(g[j]+f[i]+1),j为其儿子。
所以f[i]=(f[i+1]+1)*1/son[i]+1/son[i]*sigma(g[j]+f[i]+1);较关键的是这，因为期望步数等于这种情况发生的概率乘上该情况步数，
走到i的错节点儿子回去的期望步数为f[i]+1+g[j],乘出来移项，两个括号里的1可以合并成一个1从括号里干出来。
预处理出i节点所有错误儿子的g[]值和记为s[i],(可以直接算s[],不用算g[],省空间)。
关键点二：1/son[i]*sigma(g[i]+f[i])乘出来等于的是son[i]-1/son[i] *f[i].
移项得f[i]=son[i]+f[i+1]+s[i];
线性的...
70%算法：
这时要考虑存档点的设定了。所以设f[i][j]表示当前存档点是i还剩j次存档机会的最优解。（刚走到i更新存档点为i）
设a[i][j]表示当前存档点是i走到j的期望步数-->辅助f[i][j]转移。
a[i][j]=(a[i][j-1]+1)*1/son[j-1]+1/son[j-1]*sigma(1+g[k]+a[i][j]),k是j的错儿子,同样可以提出1合并成1个1。
问题来了为什么是+a[i][j]呢，当初真的想了两节课：（可以手动模拟一下这个过程）
走到j-1的错儿子后，再走进行读档回到的是i而不是j-1（不要和50%算法混了）。所以i到j得在走一遍，所以加上了a[i][j]而不是a[i][j-1].
移项->a[i][j]=a[i][j-1]*son[j-1]+son[j-1]+s[j-1].
预处理出a[i][j]以方便f[i][j]转移。
f[i][j]=f[k][j-1]+a[i][k],k是下一次的存档位置。
所以转移可以把i写在最外面倒序，也可以把j写在外维i则正序即可。
复杂度O(n^2p);
100%算法：..目前只学来一种还是懂了思想自己不会推的那种
摘抄出题大佬解析：
{
不过，有没有发现，70%和100%好像都没考虑一个问题。观察a数组，可以看到它是恐怖的增长的，我们最终答案会不会爆炸？
我们来估计答案的上界。考虑一种可行方案，每n/p个正确节点就设立一次存档位置，那么答案最大是多少呢？考虑最坏情况，观察a的转移，应该每变换一次存档点，大约需要3^(n/p)s[i]+3(n/p-1)*s[i+1]+3^(n/p-2)*s[i+2]+……
因为最多m个节点，s的上限是1500（实际上也远远达不到），把所有s都视为这个上限，提取公因数，计算一下那个等比数列求和，由于p是有下界的，因此n/p有上界14，发现最后也就是个12位数的样子，那么我们估计出答案最大也不会超过这个，可以放心做了。而至于a会爆炸的问题，double是可以存很多位的，而且太大的a肯定不可能被用上。
那么其实，针对答案不会特别大，a的增长又很恐怖，我们还可以思考对70%的算法优化。那就是设定一个常数step，每次转移最多从距当前step步远的位置转移过来。step取40多基本不会有问题了，因为a的下界已经是2^40了，而答案的上界远远没有达到，经过精确计算还可以再把step调小一点。
复杂度O(np log ans)
}
这种分析法还是第一次见，分析答案的上界从而卡去无用的计算。
当然感觉单队正解还是很正常的。
sd错误：清空了链向星结构体没清空head数组...
总结收获：1.根据题目数据分析部分得分算法
2.dp里一般把题目的主信息用上看是否能够转移（节点，存档点，剩余存档次数）。再加上一些预处理。
3.只颓到了这种思想，开阔眼界吧...：根据分析答案的上界和算法中数的上下界卡去无用计算，让算法飞起来。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=2500; int n,m,p; double f[maxn][maxn],a[maxn][maxn],s[maxn]; int head[maxn],cnt=1,son[maxn]; struct node{ int to,next; }line[maxn*2]; void add(int x,int y) { line[cnt].to=y; line[cnt].next=head[x]; head[x]=cnt++; son[x]++; } void dfs(int x) { for(int i=head[x];i;i=line[i].next) { int v=line[i].to; dfs(v); s[x]+=1.00/son[x]*s[v]; } s[x]+=1; } int read() { int t=0; char ch; ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') t=t*10+ch-48,ch=getchar(); return t; } int main() { int t,x,y; t=read(); while(t--) { cnt=1; memset(f,0x7f,sizeof(f)); memset(son,0,sizeof(son)); memset(s,0,sizeof(s)); memset(head,0,sizeof(head)); memset(line,0,sizeof(line)); n=read(); m=read(); p=read(); for(int i=n;i<m;i++) { x=read(); y=read(); add(x,y); } for(int i=1;i<n;i++) { son[i]++; for(int j=head[i];j;j=line[j].next) { dfs(line[j].to); s[i]+=s[line[j].to]; } } for(int i=1;i<n;i++) { a[i][i]=0; for(int j=i+1;j<=min(n,i+40);j++) { a[i][j]=a[i][j-1]*son[j-1]+son[j-1]+s[j-1]; } } for(int i=1;i<=p;i++) f[n][i]=0; for(int i=n-1;i>=1;i--) { for(int j=1;j<=p;j++) { for(int k=i+1;k<=n;k++) { if(k-i>40) break; f[i][j]=min(f[k][j-1]+a[i][k],f[i][j]); } } } printf("%.4lf ",f[1][p]); } }