blog

P1118 [USACO06FEB] Backward Digit Sums G/S

原题链接
题目范围

• \(1 \le N \le 12\)
  
• \(1 \le \text{sum} \le 12345\)
  

解题思路

这题的关键是先看出“不断相加”后的结果，本质上是一个加权和。
以 \(n=4\) 为例：

1. a1   a2   a3   a4
2.   a1+a2   a2+a3   a3+a4
3.     a1+2a2+a3   a2+2a3+a4
4.       a1+3a2+3a3+a4

复制代码

最后一行的系数是 1, 3, 3, 1，正好对应杨辉三角的一行。
继续推广可知，最终结果可以写成：

\[\sum_{i=1}^{n} a_i \cdot C(n-1, i-1)\]
于是原题就转化成了：
排列 \(a_1,a_2,\dots,a_n\)，找到一个字典序最小的方案，使得

\[\sum_{i=1}^{n} a_i \cdot C(n-1, i-1)=\text{sum}\]
所以整道题可以分成两步：

• 先预处理出杨辉三角，得到每一位对应的权值。
  
• 再用 DFS 枚举排列，计算当前加权和。
  

因为题目要求输出字典序最小的解，所以搜索时按 1 ~ n 的顺序枚举。这样第一个满足条件的方案就是答案。
剪枝

设当前已经填到第 idx 位，当前加权和为 cursum。
如果 cursum > sum，后面再怎么填也只会更大，就可以直接返回。
复杂度分析

• 时间复杂度：最坏情况下为 \(O(n! \cdot n)\)
  需要枚举排列，搜索过程中每个状态的转移是常数级，整体主要由全排列数量决定。
  
• 空间复杂度：\(O(n^2)\)
  其中杨辉三角需要 \(O(n^2)\)，递归栈、路径数组和标记数组需要 \(O(n)\)。
  n 的范围较小
  

代码实现

1. #define rep(i,a,b) for(int i=(int)a;i<int(b);++i)
3. int n, num;
4. int c[15][15];     // 杨辉三角
5. int coef[15];      // 每一位的系数
6. int path[15];      // 当前排列
7. bool used[15];
8. bool found;
10. void init() {
11.     rep(i, 0, 13) {
12.         c[i][0] = c[i][i] = 1;
13.         rep(j, 1, i) {
14.             c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
15.         }
16.     }
17. }
19. void dfs(int idx, int cursum) {
20.     if (found) return;
21.     if (cursum > num) return;
23.     if (idx == n) {
24.         if (cursum == num) {
25.             rep(i, 0, n) cout << path[i] << " ";
26.             cout << '\n';
27.             found = true;
28.         }
29.         return;
30.     }
32.     rep(i, 1, n + 1) {
33.         if (used[i]) continue;
34.         used[i] = true;
35.         path[idx] = i;
36.         dfs(idx + 1, cursum + i * coef[idx]);
37.         used[i] = false;
38.     }
39. }
41. void solve() {
42.     init();
43.     cin >> n >> num;
45.     rep(i, 0, n) {
46.         coef[i] = c[n - 1][i];
47.     }
49.     dfs(0, 0);
50. }

复制代码

易错点

• 杨辉三角的预处理
  
• DFS的使用
  
• 要按从小到大的顺序枚举，才能保证第一个找到的是字典序最小解。
  
• 剪枝条件写成 cursum > sum，不要漏掉。
  

总结

看出最后结果等价于一个组合数加权和，后面就是一个带剪枝的全排列搜索，题目规模不大

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！