首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13190

兔子不吃窝边草 有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以…

兔子不吃窝边草

有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?

时间限制:10000

内存限制:65536

输入

输入第一行给出两个正整数,即 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; pair&lt;int, vector&lt;int&gt;&gt; solve_dp(const vector&lt;int&gt;&amp; vals) { int n = vals.size(); if (n == 0) return {0, {}}; vector&lt;int&gt; dp(n, 0); dp[0] = vals[0]; if (n &gt;= 1) { dp[1] = max(vals[0], vals[1]); } for (int j = 2; j &lt; n; ++j) { dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]); } vector&lt;int&gt; selected; int j = n - 1; while (j &gt;= 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 &gt;&gt; N &gt;&gt; i; vector&lt;int&gt; arr(N); for (int j = 0; j &lt; N; ++j) { cin &gt;&gt; arr[j]; } vector&lt;int&gt; left_pos, left_vals; for (int pos = i - 2; pos &gt;= 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&lt;int&gt; left_path; for (int idx : left_idx) { left_path.push_back(left_pos[idx]); } vector&lt;int&gt; right_pos, right_vals; for (int pos = i + 2; pos &lt;= 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&lt;int&gt; right_path; for (int idx : right_idx) { right_path.push_back(right_pos[idx]); } bool choose_left = false; if (total_left &gt; total_right) { choose_left = true; } else if (total_left == total_right) { choose_left = true; } else { choose_left = false; } vector&lt;int&gt; 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 &lt;&lt; (choose_left ? total_left : total_right) &lt;&lt; endl; for (size_t k = 0; k &lt; path.size(); ++k) { if (k &gt; 0) cout &lt;&lt; " "; cout &lt;&lt; path[k]; } cout &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。