蓝桥杯算法提高VIP-种树-题解(Python代码)python开荒柘，dp法

你们很难想象我经历了什么，对，就是我拉低了正确率。。先上丑陋的代码：

n=input().split()
m=int(n[1])
n=int(n[0])
L=[int(i)+1001 for i in input().split()]
if m>int(n/2):
    print("Error!")
else:
    re1=[[0]*(n+1) for i in range(m+1)]
    re2=[[0]*(n+1) for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(3,n+1):
            if i>int(j/2):
                re1[i][j]=0
            else:
                re1[i][j]=max(re1[i][j-1],re1[i-1][j-2]+L[j-1])
    for i in range(1,m+1):
        for j in range(2,n+1):
            if i>int(j/2):
                re2[i][j]=0
            else:
                re2[i][j]=max(re2[i][j-1],re2[i-1][j-2]+L[j-1])
    print(max(re1[m-1][n-1]+L[0],re2[m][n])-m*1001)

思路：前面有一位讲过dp法的大佬和我的思路相同。由于这道题是一道环形结构，而非线性结构，dp法就会比较片面，或者说，1和n位的关系不确定。
但是可以将一个环拆成两条线，然后比较两条线的结果，取最大值
那么区别非常简单：第一个坑到底种不种
如果种，那么第二坑与第n坑就不种了，就是 在3到n-1范围内，dp【m-1】【n-1】
不种就是dp【m】【n】
然后比较
再说一下dp内部的思路，很简单就是 max(dp[i][j-1],dp[i-1][j-2]+A[j-1])
i j不满足的情况下取0
注意！由于A的值范围有负数情况，我们要手动加1001变成正数，然后再减回来
如果要更好地处理这种情况的方法，请留言，我的方法很蠢。。。