题目描述
　A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门 得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤 肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。
最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

数据规模和约定

对于全部数据，满足1< =m< =n< =30；
其中90%的数据满足m< =n< =20
-1000< =Ai< =1000

输入
输入的第一行包含两个正整数n、m。
第二行n个整数Ai。
输出
输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。
样例输入
7 3
1 2 3 4 5 6 7
样例输出
15
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

解题思路:

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;
}