列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1691
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯摆动序列 DFS -
浏览：425

蓝桥杯金陵十三钗 DFS + 剪枝
浏览：339

蓝桥杯 3000米排名预测 - DFS/全排列
浏览：260

你可能喜欢

蓝桥杯算法提高VIP-种树动态规划 / DFS (C++)

　　作者: 列公子　　　　发表时间：2020-02-22 22:46:47 浏览：944　|　评论：1　

原题链接：蓝桥杯算法提高VIP-种树

# 种树 动态规划 / DFS

## 1. 动态规划

### 1.1 最优值定义和递归关系

定义 $$dp[i][j]$$ 为 从位置 $$1$$ 到位置  $$i$$ 已经种了$$j$$棵树的情况下，美观度的最大值 （最优值）,  索引从 1 开始。

$$dp[i][j] = max(dp[i-2][j-1] + val[i], dp[i-1][j])$$

分别对应 位置 $$i$$ 种树、不种树 两种情况。

考虑到 N 个位置成环形，将问题的解分成两种情况以转变为**非环形**的子问题（从其他位置断开也可以）
- **1 号位置 种树**
	则 ```2、N``` 位置都不能种树, 问题转化为在 ```3 ～ N-1``` 这 ```N-2```个位置上种 ```M-1```棵树, 计算这个子问题时先不考虑```1```号位置的美观度，这个子问题的最优值为 ```dp[N-1][M-1] + val[1]```
- **1 号位置 不种树**
	则问题为 在 ```2 ~ N``` 这 ```N-1``` 个位置上种 ```M``` 棵树，这个子问题的最优值为 ```dp[N][M]```, 仔细处理边界值

### 1.2 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 算法提高 1551 种树
// 动态规划
//
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MIN = -1e9;
const int maxn = 35;
int N, M;

int val[maxn];      // 各个位置的数值
int dp[maxn][maxn];

int solve(){
    for (int i = 1; i <= M - 1; i++)
			dp[1][i] = dp[2][i] = MIN;

// 1 种, 则 2, N 都不种 , 转化为 在 3 ~ (n-1) 的位置种下 (m-1) 课树
    // 假设 1 未种, 最后再加上
    for (int i = 3; i < N; i++){
        for (int j = 1; j <= M - 1; j++){
            dp[i][j] = max(dp[i-2][j-1] + val[i], dp[i-1][j]);
        }
    }
    int ans1 = dp[N-1][M-1] + val[1];

// 1 不种
    memset(dp, 0, sizeof(dp));
	
    for (int i = 1; i < M+1; i++)
        dp[0][i] = dp[1][i] = MIN;

for (int i = 2; i <= N; i++){
        for (int j = 1; j <= M; j++){
            dp[i][j] = max(dp[i-2][j-1] + val[i], dp[i-1][j]);
        }
    }
    int ans2 = dp[N][M];

return max(ans1, ans2);
}

int main(){
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++){
        scanf("%d", &val[i]);
    }
    if (M > N / 2){
        printf("Error!");
        return 0;
    }
    printf("%d", solve());
    return 0;
}
```
## 2.  DFS

### 2.1 完整代码 (AC)

```cpp
//
// 蓝桥杯题库 算法提高 1551 种树
// DFS
//
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 35;
int N, M;

int val[maxn];
bool isPlanted[maxn];   // 是否种上了树
int ans = -1e9, tmp = 0;  // 最优值, 临时值

bool check(int pos){	// 是否可以种树
    if (pos > N || isPlanted[pos] || isPlanted[(pos+1) % N] || isPlanted[(pos - 1) % N])
        return false;
    return true;
}

void dfs(int pos, int cnt){      // 位置, 已经种了多少棵树
    if (cnt == M){
        ans = max(ans, tmp);
        return;
    }
    for (int i = pos; i <= N; i++){
        if (check(i)){
            tmp += val[i];
            isPlanted[i] = true;
            dfs(i, cnt+1);
            isPlanted[i] = false;
            tmp -= val[i];
        }
    }
}

int main(){
    scanf("%d%d", &N, &M);
    for (int i = 1; i < N + 1; i++)
        scanf("%d", &val[i]);
    if ( M > N / 2){
        printf("Error!");
        return 0;
    }
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}

```

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

早起床

dfs的用途是枚举每一个可能的情况，然后一个一个判断，这就有了可以用的情况和不可用的情况，数据量太大，直接寄，数据量小的话，可以一一枚举每一种情况，然而枚举每一种情况，这也是一个难点，如何定义递归结束条件，继续的条件是最重要的

2022-10-19 19:16:19

列公子

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C++代码）

C语言训练-求素数问题（C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

【明明的随机数】（C语言代码）

蓝桥杯算法提高VIP-种树动态规划 / DFS (C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

【回文数(二)】（C语言代码）

【亲和数】（C语言代码）

十->二进制转换（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

简单的a+b （C语言代码）

循环入门练习5 （C语言代码）

列公子

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C++代码）

C语言训练-求素数问题 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

【明明的随机数】 （C语言代码）

蓝桥杯算法提高VIP-种树 动态规划 / DFS (C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

【回文数(二)】 （C语言代码）

【亲和数】 （C语言代码）

十->二进制转换 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

简单的a+b （C语言代码）

循环入门练习5 （C语言代码）

C二级辅导-进制转换（C++代码）

C语言训练-求素数问题（C语言代码）

字符逆序（C语言代码）

【明明的随机数】（C语言代码）

蓝桥杯算法提高VIP-种树动态规划 / DFS (C++)

　　评论区

【回文数(二)】（C语言代码）

【亲和数】（C语言代码）

十->二进制转换（C语言代码）