蓝桥杯算法提高VIP-种树 （C++代码）（动态规划）

解题思路:

n个位置最多种植n/2棵树,n可奇可偶
    如果位置1一定需要种植一棵树，那么位置2,n一定不可以种植树，
那么需要在3-(n-1)的位置种植m-1棵树.
因为此时最大价值=dp[n-1][m-1]+A[1]

    如果位置1不种树，那么2-n的位置都可以种植树木

因为此时最大值为dp[n][m] 

    最后从两者取最优方案

    res1 = dp1[n-1][m-1]+A[1];
	res2 = dp2[n][m];
	res = max(res1,res2);

注意事项:

    边界处理需要细心一点

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 31,MIN=-0x3FFFFFFF;
int dp1[N][N],dp2[N][N],A[N]; 
int main(void)
{
	
	int n,m,res1,res2,res;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>A[i]; 
	//n个位置最多种植n/2棵树,n可奇可偶 
	if(m>n/2) 
	{
		cout<<"Error!";
		return 0;
	}
	
	
	for(int j=1;j<=m-1;j++) dp1[0][j]=dp1[1][j]=dp1[2][j]=MIN; 
	/*
	如果位置1一定需要种植一棵树，那么位置2,n一定不可以种植树，
	那么需要在3-(n-1)的位置种植m-1棵树.
	因为此时最大价值=dp[n-1][m-1]+A[1] 
	*/ 
	for(int i=3;i<=n-1;i++)//i=1,2,n不需要处理 
	{
		for(int j=1;j<=m-1;j++)//1位置一定确定种植一棵树，故只需要寻找m-1棵 
		{
			dp1[i][j]=max(dp1[i-2][j-1]+A[i],dp1[i-1][j]);
		}
	}

	for(int j=1;j<=m;j++) dp2[0][j]=dp2[1][j]=MIN;
	/*
	如果位置1不种树，那么2-n的位置都可以种植树木
	因为此时最大值为dp[n][m] 
	*/
	for(int i=2;i<=n;i++)//i=1不需要处理 
	{
		for(int j=1;j<=m;j++)
		{
			dp2[i][j]=max(dp2[i-2][j-1]+A[i],dp2[i-1][j]);
		}
	}
	
	res1 = dp1[n-1][m-1]+A[1];
	res2 = dp2[n][m];
	res = max(res1,res2);
	
	cout<<res;
	return 0;
}