NOIP训练赛 #1

T1 奇怪的冰雹

【数据范围】

\(1 \leq n \leq 4,1 \leq m \leq 120,1 \leq a_i \leq 50\)

由于 \(n\) 的范围过于小,顾考虑用DP来解决

状态设计:设 \(dp_{i,j,k,l}\) 表示 \(4\) 个木桶的完好度分别为 \(i,j,k,l\) 时的概率( \(i,j,k,l>=0\) ),那么被砸坏的概率就是 \(1.0-dp_{i,j,k,l}\)

状态转移:注意到最多能将落的有效冰雹次数为 \(\min(m,\sum_{i=1}^4a_i)\) ,故可以枚举 \(i,j,k\) 来算出 \(l\) ,如果合法则转移

转移方程:

设 \(K=i+j+k+l\)

则有:

• \(dp_{i-1,j,k,l}+=\frac{dp_{i,j,k,l}}{K}[i>=1]\)
• \(dp_{i,j-1,k,l}+=\frac{dp_{i,j,k,l}}{K}[j>=1]\)
• \(dp_{i,j,k-1,l}+=\frac{dp_{i,j,k,l}}{K}[k>=1]\)
• \(dp_{i,j,k,l-1}+=\frac{dp_{i,j,k,l}}{K}[l>=1]\)

T2 划分序列

题解

区间DP板子题,枚举断点即可

时间复杂度 \(O(n^2k)\)

T3 智能小球

首先用 \(Floyd\) 求全源最短路