CSP-J 2020 第一轮 第 32 题：程序（三）：30个0和30个5的输出

题目

#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$ 为 $30$，接下来的输入是 $30$ 个 $0$ 和 $30$ 个 $5$，则输出为（ ）。

选项

• A. 2000
• B. 2010
• C. 2030
• D. 2020

答案

C

题解

选 C．2030。

这段程序会枚举所有“合并相邻两组”的顺序，并用 ans 保存总得分的最大值。

1. 每次合并的得分是什么？

第一列全是 0，无论怎样合并，仍然都是 0，所以：

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

就等于 abs(b - y)。

第二列初始都是 5。如果相邻两组分别包含 \(p\)、\(q\) 个原始元素，它们的值就是 \(5p\)、\(5q\)，因此合并得分为：

\[ 5|p-q| \]

2. 怎样合并可以得到最大值？

从左边开始，每次把已经合并的大组与右边的一个 5 合并：

总得分为：

\[ 0+5+10+\cdots+140 =5(0+1+\cdots+28) =5\times\frac{28\times29}{2} =\boxed{2030} \]

3. 为什么不会有更大的答案？

第 \(t\) 次合并前，还剩 \(30-t+1\) 组。除去本次合并的两组，其余 \(29-t\) 组每组至少包含一个原始元素，所以本次两组最多包含：

\[ 30-(29-t)=t+1 \]

个原始元素。两组各至少有一个元素，故数量差最多为 \(t-1\)，本次得分最多为 \(5(t-1)\)。

上面的合并方式每一步都达到了这个上限，因此总分 2030 就是最大值。