esc to dismiss
x
Home / week-85 / 837

信息

题解

Tip

获得 k 分或更多分时, 停止抽取数字, 最大抽取max_pts
因此最终停止的分数范围为 [k, k-1+max_pts]
可以视为, 总台阶数k, 单次最多max_pts
* 进而变成了初始台阶为0, 如何跳到k

用 dp[i] 存从台阶i到最终停止不超过n的概率
假设从i 能跳到j, 则 \(dp[i] = \sum dp[j] / max\)
* j 的取值范围 [1, max_pts]
* 不同链路之间是加法关系
* 相同链路的不同步之间是乘法关系
初始状态下, dp[k..=n..min(k-1+max_pts)] = 1.0

实现1

Warning
  • 复杂度\(O(n + k * max_pts)\)
  • 会超时 
pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
    if k == 0 {
        return 1.0f64;
    }
    let mut dp = vec![0.0f64; (k + max_pts) as usize];
    for i in k..=n.min(k+max_pts-1){
        dp[i as usize] = 1.0;
    }
    for i in (0..k as usize).rev() {
        for j in 1..=max_pts as usize {
            dp[i] += dp[i + j].div(max_pts as f64);
        }
    }
    dp[0]
}

实现2

\[ \begin {align} &\because dp[i] = \frac{\sum_{s=1}^{max} dp[i+s]}{max} \\\\ &\therefore dp[i+1] - dp[i] \\\\ &= \frac{\sum_{s=1}^{max} dp[i+1+s] - \sum_{s=1}^{max} dp[i+s]}{max} \\\\ &= \frac{\sum_{s=1}^{max} dp[i+1+s] - \sum_{s=1}^{max-1} dp[i+1+s] - dp[i+1]}{max} \\\\ &= \frac{dp[i+1+max]-dp[i+1]}{max} \\\\ &\therefore dp[i] = dp[i+1] - \frac{dp[i+1+max]-dp[i+1]}{max} \end {align} \]
pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
    if k == 0 {
        return 1.0f64;
    }
    let mut dp = vec![0f64; (k + max_pts) as usize];
    for i in k..=n.min(k - 1 + max_pts) {
        dp[i as usize] = 1.0f64;
    }
    dp[k as usize - 1] = (max_pts.min(n - k + 1) as f64) / (max_pts as f64); // O(1) 计算 dp[k-1]
    for i in (0..k - 1).rev() {
        let i = i as usize;
        dp[i] = dp[i + 1] - (dp[i + max_pts as usize + 1] - dp[i + 1]).div(max_pts as f64);
    }
    dp[0]
}

复杂度 \(O(min(n,k+maxPts))\)

Backlinks

Tags

x