编写题解 1551: 蓝桥杯算法提高VIP-种树 一点点想法

解题思路:分两种情况，要么选首元素，要么选尾元素，避免首尾冲突

注意事项:n=1时，仅m=1有效  

环形数组选不相邻m个，有效范围是 1<=m<=n/2

参考代码:

#include<stdio.h>

int n, m;

int arr[100];

long long max_sum = -1e18;

void fun(int now, int last, int left, long long sum, int start, int end) {

    if (left == 0) {

        if (sum > max_sum) max_sum = sum;

        return;

    }

    if (now > end) return;

    fun(now + 1, last, left, sum, start, end);

    if (last == -1 || now - last > 1) {

       fun(now + 1, now, left - 1, sum + arr[now], start, end);

    }

}

int main() {

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {

        scanf("%d", &arr[i]);

    }

    if (n == 1 && m == 1) {  // 特殊情况：n=1时，仅m=1有效

        printf("%d\n", arr[0]);

        return 0;

    }

    //环形数组选不相邻m个，有效范围是 1<=m<=n/2

    if (m > 0 && m <= n / 2) {

        fun(1, -1, m, 0, 1, n - 1);  // 不选首元素

        fun(0, -1, m, 0, 0, n - 2);  // 不选尾元素

    }

    if (max_sum == -1e18) {

        printf("Error!\n");

    } else {

        printf("%lld\n", max_sum);

    }

    return 0;

}