第一题:完美序列 90%
n=int(input()) nums1=list(map(int,input().split())) nums2=list(map(int,input().split())) m=int(input()) nums3=list(map(int,input().split())) nums4=list(map(int,input().split())) if (nums1[0] not in nums3) and (nums2[0] not in nums4): print(0) else: for i in range(m): if i>m-n: print(0) break else: if nums3[i]==nums1[0]: cur=0 Flag=True for j in range(i,i+n): if nums3[j]==nums1[cur] and nums4[j]==nums2[cur]: cur+=1 else: Flag=False break if Flag==True: print(i+1) break
第二题:最长递减子序列,一开始用dp,发现不对,还可以向上走,改用dfs。
n,m=map(int,input().split()) path,res=[],[] for _ in range(n): path=list(map(int,input().split())) res.append(path) direct=[(0,1),(0,-1),(-1,0),(1,0)] dp=[[0]*m for _ in range(n)] def dfs(i,j): if dp[i][j]!=0: return dp[i][j] dp[i][j]=1 for dx,dy in direct: x,y=i+dx,j+dy if 0<=x<n and 0<=y<m and res[x][y]<res[i][j]: dp[i][j]=max(dp[i][j],1+dfs(x,y)) return dp[i][j] max_=0 for i in range(n): for j in range(m): max_=max(max_,dfs(i,j)) print (max_)第三题:二叉树最大异或路径和(类似)
递归写的,不知哪里出错了,全局变量处理错了,不会。
全部评论
(13) 回帖