CSP-J 2020 第一轮 第 33 题：程序（三）：15,14,...,1两组序列的输出

题目

#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$ 的正整数，完成下面的判断题和单选题：

（4 分）若输入的 $n$ 为 $15$，接下来的输入是 $15$ 到 $1$，以及  $15$ 到 $1$，则输出为（ ）。

选项

• A. 2440
• B. 2220
• C. 2240
• D. 2420

答案

C

题解

选 C．2240。

dfs 枚举所有“合并相邻两项”的顺序，ans 保存最大的总得分。

由于输入的两组序列相同，而且合并时两列分别相加，所以始终有 a == b、x == y。每次合并的得分因此为： \[ s=a+x+|a-x|=2\max(a,x). \]

最优方案是从左到右，将已经合并的部分不断与下一项合并：

为什么这样一定最优？在第 \(k\) 次合并前，只进行过 \(k-1\) 次合并，因此任意一项最多包含原来的 \(k\) 个数，其值最多为最大的 \(k\) 个数之和： \[ 15+14+\cdots+(16-k). \] 所以第 \(k\) 次得分最多是这个和的两倍。上述方案每次都能达到这个上限，因此总得分最大。

共合并 \(14\) 次，故输出： \[ \begin{aligned} ans &=2\sum_{k=1}^{14}\frac{k(31-k)}2\\ &=31\sum_{k=1}^{14}k-\sum_{k=1}^{14}k^2\\ &=31\times105-1015\\ &=\boxed{2240}. \end{aligned} \]