CSP-J 2020 第一轮 第 28 题：程序（三，相邻合并求最大代价）：n=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$ 为 $0$，此程序可能会死循环或发生运行错误。（ ）

选项

• A. 正确
• B. 错误

答案

B

题解

答案：B. 错误。

当输入 n = 0 时：

1. main 中两个输入数组的循环都不执行，随后令 ans = 0，调用 dfs(0, 0)。
2. 在 dfs 中，n == 1 不成立，继续执行到：

``cpp for (int i = 1; i < n; ++i) ` 初始条件 1 < 0` 为假，因此循环体不执行，也就不会访问数组或进行递归调用。

1. dfs 执行到函数末尾，正常返回，最后输出 0。

关键点：没有进入 n == 1 的分支，不代表一定会继续递归；这里循环不执行，函数同样会结束。