CSP-J 2020 第一轮 第 31 题：程序（三）：20个9和20个0的输出

题目

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
  if (n == 1) {
    ans = max(sum, ans);
    return;
  }
  for (int i = 1; i < n; ++i) {
    int a = d[i - 1][0], b = d[i - 1][1];
    int x = d[i][0], y = d[i][1];
    d[i - 1][0] = a + x;
    d[i - 1][1] = b + y;
    for (int j = i; j < n - 1; ++j)
      d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
    int s = a + x + abs(b - y);
    dfs(n - 1, sum + s);
    for (int j = n - 1; j > i; --j)
      d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
    d[i - 1][0] = a, d[i - 1][1] = b;
    d[i][0] = x, d[i][1] = y;
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
  cin >> d[i][0];
  for (int i = 0; i < n;++i)
     cin >> d[i][1];
  ans = 0;
  dfs(n, 0);
  cout << ans << endl;
  return 0;
}

假设输入的 $n$ 是不超过 $50$ 的正整数，d[i][0]、d[i][1] 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

若输入的 $n$ 为 $20$，接下来的输入是 $20$ 个 $9$ 和 $20$ 个 $0$，则输出为（ ）。

选项

• A. 1890
• B. 1881
• C. 1908
• D. 1917

答案

B

题解

答案是 B．1881。

这段程序会枚举所有“合并相邻两项”的顺序，ans 记录合并得分总和的最大值。

1. 每次合并的得分是多少？

输入的第二列全是 0，合并后也一直是 0，因此：

``cpp s = a + x + abs(b - y) = a + x; ``

也就是说，每次得分等于新合并出来的数。例如两个 9 合并成 18，这次就得 18 分。

2. 怎样让总得分最大？

让已经合并出的数不断与旁边的一个 9 合并：

``text 9 + 9 → 18，得 18 分 18 + 9 → 27，得 27 分 27 + 9 → 36，得 36 分 …… 171 + 9 → 180，得 180 分 ``

为什么这样一定最大？第 \(t\) 次合并时，一个合并块最多包含 \(t+1\) 个原始的 9，所以这次得分最多为 \(9(t+1)\)。上面的方案每次都达到了这个上限，并且符合“相邻合并”的要求。

20 个数共合并 19 次，因此最大总分为：

\[ \begin{aligned} ans &= 18+27+36+\cdots+180\\ &=9(2+3+\cdots+20)\\ &=9\left(\frac{20\times21}{2}-1\right)\\ &=\boxed{1881}. \end{aligned} \]