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\) 求全源最短路