A17117. 侗族鼓楼游客规划
填空题
中等
知识点
题目描述
侗族鼓楼游客规划
题目描述
侗族鼓楼景区有 n 个观景台，编号 1~n，每个观景台有对应的游客承载量。景区规定：相邻观景台不能同时满员。现给出各观景台的最大承载量，需要计算景区最多能容纳的游客总数，合理规划观景台开放方案，保障游览安全。
输入格式
第一行输入一个整数 n（4≤n≤15），表示观景台数量；
第二行输入 n 个整数，依次为每个观景台的最大承载量（10≤承载量≤100）。
输出格式
输出一个整数，表示景区最多可容纳的游客总数。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[20];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int dp[20] = {0};
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for(int i = 2; i < n; i++) {
dp[i] = max(dp[i-1], dp[i-2] + a[i]);
}
cout << dp[n-1] << endl;
return 0;
}答案解析
将问题转化为在序列中选择若干不相邻位置的元素，使其和最大。使用动态规划，定义状态 dp[i] 表示前 i 个观景台能容纳的最大游客数。状态转移时，考虑第 i 个观景台是否开放：若开放，则不能开放第 i-1 个，即 dp[i] = dp[i-2] + capacity[i]；若不开放，则继承 dp[i-1]。取两者较大值更新 dp[i]。初始化 dp[0] = 0，dp[1] = capacity[0]。从 i=2 开始递推至 n，最终结果为 dp[n]。
上一题
下一题