爱奇艺笔试第二题思路

第一题是leetcode903原题 第二题动态规划:dp[i][j]表示i个红球和j个蓝球A的获胜概率.如果i=0,dp[i][j]=0.如果j=0,dp[i][j]=1.否则的话dp[i][j]由下列步骤求得: dp[i][j]+=i/(i+j);//表示A直接取得红球的概率 如果j=1,那么dp[i][j]+=0.A取蓝球之后,B肯定获胜 如果j=2,dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*dp[i-1][j-2];j/(i+j)是A取蓝球的概率,在A取蓝球的基础上B再取蓝球A才有获胜机会,所以(j-1)/(i+j-1)表示B再取蓝球的概率,然后C只能从红球选一个,在ABC选一轮后,A的获胜概率就要加上dp[i-1][j-2],所以A获胜的概率为j/(i+j)*(j-1)/(i+j-1)*dp[i-1][j-2]; 如果j>2,dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*(i/(i+j-2)*dp[i-1][j-2]+(j-2)/(i+j-2)*dp[i][j-3]);i/(i+j-2)*dp[i-1][j-2]+(j-2)/(i+j-2)*dp[i][j-3]表示A从蓝球选一个,B从蓝球选一个后,C分别从红球蓝球取出一个的A的获胜概率.

#include<bits/stdc++.h> using namespace std; int main() {     int n,m;     cin>>n>>m;     double dp[n+1][m+1];     for(int i=0;i<n+1;i++) {dp[i][0]=1;}     for(int i=0;i<m+1;i++) {dp[0][i]=0;}     dp[0][0]=0;     for(int x=1;x<n+1;x++) {         for(int y=1;y<m+1;y++) {             double i=x,j=y,p1=i/(i+j),p2=j/(i+j),p3=0,p4=0;             if (y-2>=0) p3=p2*(i/(i+j-1))*((j-1)/(i+j-2));             if (y-3>=0) p4=p2*((j-1)/(i+j-1))*((j-2)/(i+j-2));             dp[x][y]=p1+p3*dp[x-1][y-2]+p4*dp[x][y-3];         }     }     printf("%.5f",dp[n][m]);     return 0; }

第二题AC思路如下：

第一题，直接输出3，过18…… 第二题，直接计算第一轮A拿到红球，n/n+m，过9……我太菜了

递推或者递归

第一题36的代码就是全排列，然后长度等于n的话就做条件验证。  类似的题见https://www.luogu.org/problem/P2606。看大佬们看不看得懂了。

算了先删掉等结束再放吧= =

第二题ac思路：

弱渣做法…求出所有1-n的全排列 然后一个个判断 只过18 比较这样会超时…

求代码

27的路过

第一题剪枝只过36，

第一题有思路嘛