爱奇艺笔试答题1

leetcode903

第二题有思路吗，完全不会啊

#include <iostream> #include <vector> #include <iomanip> using namespace std; double frac(int m,int n){     double c = m * 1.0/n;     return c; } int main() {     int n,m;cin>>n>>m;     vector<vector<double>> dp(n + 1,vector<double> (m + 1,0.0));     for(int i = 1;i <= n;i++)dp[i][0] = 1.0;     for(int i = 1;i <= n;i++){         for(int j = 1;j <= m;j++){             dp[i][j] += i * 1.0/ (i + j);             if(i - 1 >= 0 && j - 2 >= 0)                 dp[i][j] += frac(j,i + j) * frac(j - 1,i + j - 1) * frac(i,i + j - 2) * dp[i - 1][j - 2];             if(j - 3 >= 0)                 dp[i][j] += frac(j,i + j) * frac(j - 1,i + j - 1) * frac(j - 2,i + j - 2) * dp[i][j - 3];         }     }     cout<<fixed<<setprecision(5)<<dp[n][m]<<endl;     return 0; }

同问啊

求解

同求

同求，，，也求第二题

本想暴力dfs。肯定50%都过不了就懒得写了，

已经交卷了，实在想不出来

python只能A36%....， 感觉换个语言能好很多

有答案吗

求答案

两题都是动态规划

感觉是动态规划但是没规划出来😂

两道题都是用动态规划写。但是要面好未来，只用了30分钟答了一下题。过了36%的case就没管了，估计是没得机会了吧😢

1 0.45

切方块的可以用贪心，用C++唯一的坑在溢出要用long long 这道感觉更像数学 反正我无力了最后剩20分钟写了个DFS遍历过了快40%交卷跑路

全排列以后再判断吧,  做第二题花的时间有点多 第一道题没来得及调试.....只A了一道

求思路啊

#[i for i in a if not 2==i] def ys(mem,ln,ai):     print(mem)     co = 0     if len(ln)==0:return True     if A[ai]==0:         for idx,c in enumerate(ln):             tf = True             if c>mem[-1]:                 zz = [i for i in ln if not c==i]                 tf = tf and ys(mem+[c],zz,ai+1)             else:tf = False#;return False             if tf:co+=1     elif A[ai]==1:         for idx,c in enumerate(ln):             tf = True             if c<mem[-1]:                 zz = [i for i in ln if not c==i]                 tf = tf and ys(mem+[c],zz,ai+1)             else:tf = False#;return False             if tf:co+=1     return co #N = int(input().strip()) #A = [int(i) for i in input().strip().split()] N = 4#int(input().strip()) A = [1,1,0]#[int(i) for i in input().strip().split()] def so():     if N<=0 :return 0     if N ==1:return 1     ln = [i for i in range(1,N+1)]     tmp = []     count = 0     for idx,c in enumerate(ln):         tmp = [c]         zz= [i for i in ln if not c==i]         #import pdb;pdb.set_trace()         count += ys(tmp,zz,0)     return count print(so())