K点游戏

http://www.nowcoder.com/questionTerminal/8e724c53f15d47b29d4b58208b3902df

题目难度：三星
考察点：动态规划、前缀和

方法1：动态规划

1.分析：

这个题其实可以采用动态规划的思想来做，我们设 dp[n] 表示的是当前点数为 n 的概率，如果不考虑 K 的话,那么就有dp[n]的公式如下

$dp[n]=\frac {dp[n-1]}w+\frac {dp[n-2]}w+...+\frac {dp[n-w]}w ; w\le n$

这里解释一下这个公式，其实就是看dp[n]是怎么来的，假设我们在[1,w]中随机抽取一个整数x，那么dp[n]就可以通过dp[n-x]+x来，即dp[n]=dp[n-x]/w，那么x的可以取值范围为[1,w]，所以dp[n]的公式就如上式。

举个例子：假设n=10， w=5，那么dp[10]可以由[1, 2, 3, 4, 5]中的任意一个数对应的加上[9,8,7,6,5]得到。所以，其中p(i)表示抽到点i的概率。

那么我们如果考虑上K 就会有一些点数不满足情况而被剔除，比如说假设上例的k=8，那么dp[9]和dp[8]就会被舍弃，因为在题目中要求不能大于等于k，所以上述的dp[10]=dp[7]*p(3)+dp[6]*p(4)+dp[5]*p(5)，然后推出通项公式为：

$dp[n]=\frac {dp[k-1]}w+\frac {dp[k-2]}w+...+\frac {dp[n-w]}w ; w\le n$

根据推出的公式我们就可以计算了，首先初始化dp[0]=1,然后计算左右边界注意左边界为max(n-w, 0)，右边界为min(n-1, k-1)，所以我们可以通过自底向上的方法一步步求出dp[n]，然后在求一个加和 $\sum_{i=K}^Ndp[i]$ ，因为这个题的下届是K，上届是N。

算法实现：

(1). 输入对应的n,k,w。
(2).初始化dp[0]=1。

(3). 根据状态转移方程进行循环，自底向下求dp[i]。

(4). 根据求得的dp[i]，然后对区间[k, n]内所有dp加和

(5). 输出加和结果

2.复杂度分析：

时间复杂度：O(n^2)
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
double dp[MAXN];
int main(){
    int n, k, w; cin>>n>>k>>w;
    dp[0] = 1;
    for(int i=1; i<=n; i++) {
        int l = max(0, i-w), r = min(i-1, k-1);
        for(int j=l; j<=r; j++) dp[i] += dp[j] / w;
    }
    double ans = 0;
    for(int i=k; i<=n; i++) ans += dp[i];
    printf("%.5f\n",ans);
    return 0;
}

方法2：动态规划、前缀和

1.分析：

上述的方法其实已经能够AC这个题了，但是我们还有一个更优化的方法，就是在加和的时候不需要真正的进行从区间[l,r]的加和，只需要利用一个前缀和数组sum就可以避免循环加和的操作，sum[i]表示区间[1,i]的所有概率的和，那么区间[l,r]的和就可以表示为sum[r]-sum[l-1]，利用前缀和可以优化时间复杂度为O(n)，具体详见代码。

算法实现：

(1). 输入n, k, w。

(2). 初始化dp[0]=1。

(3). 根据状态转移方程进行循环，自底向下求dp[i]，求dp[i]的时候顺带求一下sum[i] = sum[i-1] + dp[i]。

(4). 输出sum[n] - sum[k-1]

2.复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
double dp[MAXN], sum[MAXN];
int main(){
    int n, k, w; cin>>n>>k>>w;
    dp[0] = 1, sum[0] = 1;
    for(int i=1; i<=n; i++) {
        int l = max(0, i-w), r = min(i-1, k-1);
        dp[i] = (sum[r] - sum[l-1]) / w;
        sum[i] = sum[i-1] + dp[i];
    }
    printf("%.5f\n",sum[n] - sum[k-1]);
    return 0;
}