美团校招算法题抽牌动态规划

Bertha 。 2022-04-23 06:10 110阅读 0赞

问题描述：桌上有n张牌，编号为1到n，每张牌上有一个数字，第i张牌的数字为![\\small \{a\_\{i\}\}][small _a_i]，现在小方和小明两个人玩游戏，轮流抽牌，每人一次只能抽一张牌，小明先抽。每次抽牌只能抽取最上面的牌或者最下面的牌，他们两个都是随机抽取，小明每次抽取上面的牌的概率为p，抽取下面的牌的概率为1-p。小方每次抽取上面的牌的概率为q，抽取下面的概率为1-q。最后他们的得分为所有牌上的数字之和，求小明的分数期望。

输入描述：第一行为三个数，![\\small n,P,Q(0\\leq n\\leq 1000, 0\\leq P\\leq 100,0\\leq Q\\leq 100), p = P/100, q = Q/100][small n_P_Q_0_leq n_leq 1000_ 0_leq P_leq 100_0_leq Q_leq 100_ p _ P_100_ q _ Q_100] , 第二行为n个数，为每张牌上的分数。

解题思路：首先应该想到这个题的暴力解法，小方和小明每次都有两种抽取的方法，每一种方法小明都可以得到一个分数，然后将这些分数和概率相乘，然后把所有的结果相加就能得到小明分数的期望，时间复杂度为指数级，代码如下：

#include<iostream>
    #include<vector>
    using namespace std;
    float fb(vector<int> arr, int i, int j, float p, float q, float p_all, int m){
        if(i == j){
            return (m + arr[i])*p_all;
        }
        if(i == j - 1){
            return (m + arr[i]) * p * p_all + (m + arr[j]) * (1 - p) * p_all;
        }
        return fb(arr, i + 2, j, p, q, p_all * p * q, m + arr[i]) +
               fb(arr, i + 1, j - 1, p, q, p_all * p * (1 - q), m + arr[i]) +
               fb(arr, i, j - 2, p, q, p_all * (1 - p) * (1 - q), m + arr[j]) +
               fb(arr, i + 1, j - 1, p, q, p_all * (1 - p) * q, m + arr[j]);
        
            
    }
    int main(){
        int n;
        int a;
        int b;
        while(cin >> n >> a >> b){
            float p = a / 100.0;
            float q = b / 100.0;
            vector<int> arr(n, 0);
            for(int i = 0; i < n; i++){
                cin >> arr[i];
            }
            printf("%.3f",  fb(arr, 0, n - 1, p, q, 1, 0));
        }
        return 0;
    }

但是，这种方法时间复杂度太高，不能AC，只能解决40%的数据。但是，有一点刷题经验的人都知道这种指数级别的时间复杂度，大部分都能够通过动态规划的方法来解决，这个题也一样。我们用dp\[i\]\[j\]表示从i到j这些数小明能够获得的得分期望，我们可以得到递推公式：

![\\small dp\[i\]\]\[j\]=p\*(q\*dp\[i+2\]\[j\]+(1 - q)\*dp\[i+1\]\[j-1\]+arr\[i\])\\\\+(1-p)\*(q\*dp\[i+1\]\[j-1\]+(1- q)\*dp\[i\]\[j-2\]+arr\[j\])][small dp_i_j_p_q_dp_i_2_j_1 - q_dp_i_1_j-1_arr_i_1-p_q_dp_i_1_j-1_1- q_dp_i_j-2_arr_j]

这里的arr\[i\]为第i张牌的数字。代码如下：

#include<iostream>
    #include<vector>
    using namespace std;
    int main(){
        int n;
        int a;
        int b;
        while(cin >> n >> a >> b){
            double p = a / 100.0;
            double q = b / 100.0;
            vector<int> arr(n, 0);
            for(int i = 0; i < n; i++){
                cin >> arr[i];
            }
            vector<vector<double>> dp(n, vector<double>(n, 0));
            for(int i = 0; i < n; i++){
                dp[i][i] = arr[i];
                if(i < n - 1){
                    dp[i][i + 1] = p * arr[i] + (1 - p) * arr[i + 1];
                }
            }
    	for(int l = 2; l <= n - 1; l++){
    	  for(int i = 0; i < n - l; i++){
    		int j = i + l; 
    		dp[i][j] = p*(q * dp[i + 2][j] + (1 - q) * dp[i + 1][j - 1] + arr[i]) 
    					  + (1 - p)*(q * dp[i + 1][j - 1] + (1 - q) * dp[i][j - 2] +arr[j]);
    		}
    	}
    	printf("%.3f", dp[0][n - 1]);
        }
        return 0;
    }

时间复杂度为![\\small O(n^\{2\})][small O_n_2]，注意要用double，用float有一些数据通不过。

[small _a_i]: https://private.codecogs.com/gif.latex?%5Csmall%20%7Ba_%7Bi%7D%7D
[small n_P_Q_0_leq n_leq 1000_ 0_leq P_leq 100_0_leq Q_leq 100_ p _ P_100_ q _ Q_100]: https://private.codecogs.com/gif.latex?%5Csmall%20n%2CP%2CQ%280%5Cleq%20n%5Cleq%201000%2C%200%5Cleq%20P%5Cleq%20100%2C0%5Cleq%20Q%5Cleq%20100%29%2C%20p%20%3D%20P/100%2C%20q%20%3D%20Q/100
[small dp_i_j_p_q_dp_i_2_j_1 - q_dp_i_1_j-1_arr_i_1-p_q_dp_i_1_j-1_1- q_dp_i_j-2_arr_j]: https://private.codecogs.com/gif.latex?%5Csmall%20dp%5Bi%5D%5D%5Bj%5D%3Dp*%28q*dp%5Bi&plus;2%5D%5Bj%5D&plus;%281%20-%20q%29*dp%5Bi&plus;1%5D%5Bj-1%5D&plus;arr%5Bi%5D%29%5C%5C&plus;%281-p%29*%28q*dp%5Bi&plus;1%5D%5Bj-1%5D&plus;%281-%20q%29*dp%5Bi%5D%5Bj-2%5D&plus;arr%5Bj%5D%29
[small O_n_2]: https://private.codecogs.com/gif.latex?%5Csmall%20O%28n%5E%7B2%7D%29