python-种树（递归）

解题思路:

递归。

注意事项:

参考代码:

def dfs(x,cnt,now):    
    global n,m,A,vis,ans    
     
    if cnt == m:    
        if now > ans:    
            ans = now    
        return    
         
    if n-x < 2*(m-cnt)-1:  #重要优化  
        return    
     
    if x == 0:    
        if (not vis[x]) and (not vis[x+1]) and (not vis[n-1]):    
            vis[x] = 1    
            for i in range(x+1,n+1):    
                dfs(i,cnt+1,now+A[x])    
            vis[x] = 0    
        else:    
            for i in range(x+1,n+1):    
                dfs(i,cnt,now)    
    elif x == n-1:    
        if (not vis[x]) and (not vis[x-1]) and (not vis[0]):    
            vis[x] = 1    
            for i in range(x+1,n+1):    
                dfs(i,cnt+1,now+A[x])    
            vis[x] = 0    
        else:    
            for i in range(x+1,n+1):    
                dfs(i,cnt,now)    
    else:    
        if (not vis[x]) and (not vis[x-1]) and (not vis[x+1]):    
            vis[x] = 1    
            for i in range(x+1,n+1):    
                dfs(i,cnt+1,now+A[x])    
            vis[x] = 0    
        else:    
            for i in range(x+1,n+1):    
                dfs(i,cnt,now)         
             
                         
if __name__ == '__main__':    
    n,m = map(int,input().strip().split())    
    A = [int(i) for i in input().strip().split()]    
    vis = [0 for i in range(n)]    
    ans = 0    
    if n < 2*m-1:    
        print('Error!')    
    else:    
        for i in range(n-(2*m-2)):    
            dfs(i,0,0)    
        print(ans)