A29402. 兔子不吃窝边草
填空题
较难
知识点
题目描述
兔子不吃窝边草
题目描述
有谚语云：“兔子不吃窝边草”。现给定若干块排列成一条线的草皮，假设兔子从任何一块草皮开始吃，但吃完一块后，绝对不吃直接相邻的草皮，则兔子最多可以吃掉多少草？
输入
输入第一行给出两个正整数，即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103)，以空格分隔，依次表示每块草皮的含草量。
输出
首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔，行首尾不得有多余空格。 注意：我们必须假设兔子只朝一个方向跳着吃草，否则如果它可以来回跳，就能吃掉所有的草了。如果朝左右两个方向得到的结果一样，则兔子总是喜欢向左边跳；并且如果有多块草皮都可以得到同样的结果，兔子总是选择跳到离自己最近的那块。
样例输入
样例1：
10 4
2 1 4 3 1 1 5 2 3 1样例2：
10 8
2 1 4 3 1 1 5 2 3 1样例输出
样例1：
11
4 7 9样例2:
9
8 6 3 1参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, vector<int>> solve_dp(const vector<int>& vals) {
int n = vals.size();
if (n == 0) return {0, {}};
vector<int> dp(n, 0);
dp[0] = vals[0];
if (n >= 1) {
dp[1] = max(vals[0], vals[1]);
}
for (int j = 2; j < n; ++j) {
dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]);
}
vector<int> selected;
int j = n - 1;
while (j >= 0) {
if (j == 0) {
selected.push_back(j);
break;
}
if (dp[j] == dp[j - 1]) {
--j;
} else {
selected.push_back(j);
j -= 2;
}
}
reverse(selected.begin(), selected.end());
return {dp.back(), selected};
}
int main() {
int N, i;
cin >> N >> i;
vector<int> arr(N);
for (int j = 0; j < N; ++j) {
cin >> arr[j];
}
vector<int> left_pos, left_vals;
for (int pos = i - 2; pos >= 1; --pos) {
left_pos.push_back(pos);
left_vals.push_back(arr[pos - 1]);
}
auto [left_sum, left_idx] = solve_dp(left_vals);
int total_left = arr[i - 1] + left_sum;
vector<int> left_path;
for (int idx : left_idx) {
left_path.push_back(left_pos[idx]);
}
vector<int> right_pos, right_vals;
for (int pos = i + 2; pos <= N; ++pos) {
right_pos.push_back(pos);
right_vals.push_back(arr[pos - 1]);
}
auto [right_sum, right_idx] = solve_dp(right_vals);
int total_right = arr[i - 1] + right_sum;
vector<int> right_path;
for (int idx : right_idx) {
right_path.push_back(right_pos[idx]);
}
bool choose_left = false;
if (total_left > total_right) {
choose_left = true;
} else if (total_left == total_right) {
choose_left = true;
} else {
choose_left = false;
}
vector<int> path;
path.push_back(i);
if (choose_left) {
for (int pos : left_path) {
path.push_back(pos);
}
} else {
for (int pos : right_path) {
path.push_back(pos);
}
}
cout << (choose_left ? total_left : total_right) << endl;
for (size_t k = 0; k < path.size(); ++k) {
if (k > 0) cout << " ";
cout << path[k];
}
cout << endl;
return 0;
}
上一题
下一题