P1118 [USACO06FEB] Backward Digit Sums G/S

1≤≤121≤sum≤12345解题思路这题的关键是先看出“不断相加”后的结果本质上是一个加权和。以 4 为例a1 a2 a3 a4 a1a2 a2a3 a3a4 a12a2a3 a22a3a4 a13a23a3a4最后一行的系数是1, 3, 3, 1正好对应杨辉三角的一行。继续推广可知最终结果可以写成∑1⋅(−1,−1)于是原题就转化成了排列 1,2,…,找到一个字典序最小的方案使得∑1⋅(−1,−1)sum所以整道题可以分成两步先预处理出杨辉三角得到每一位对应的权值。再用 DFS 枚举排列计算当前加权和。因为题目要求输出字典序最小的解所以搜索时按1 ~ n的顺序枚举。这样第一个满足条件的方案就是答案。剪枝设当前已经填到第idx位当前加权和为cursum。如果cursum sum后面再怎么填也只会更大就可以直接返回。复杂度分析时间复杂度最坏情况下为 (!⋅)需要枚举排列搜索过程中每个状态的转移是常数级整体主要由全排列数量决定。空间复杂度(2)其中杨辉三角需要 (2)递归栈、路径数组和标记数组需要 ()。n 的范围较小代码实现#define rep(i,a,b) for(int i(int)a;iint(b);i) int n, num; int c[15][15]; // 杨辉三角 int coef[15]; // 每一位的系数 int path[15]; // 当前排列 bool used[15]; bool found; void init() { rep(i, 0, 13) { c[i][0] c[i][i] 1; rep(j, 1, i) { c[i][j] c[i - 1][j - 1] c[i - 1][j]; } } } void dfs(int idx, int cursum) { if (found) return; if (cursum num) return; if (idx n) { if (cursum num) { rep(i, 0, n) cout path[i] ; cout \n; found true; } return; } rep(i, 1, n 1) { if (used[i]) continue; used[i] true; path[idx] i; dfs(idx 1, cursum i * coef[idx]); used[i] false; } } void solve() { init(); cin n num; rep(i, 0, n) { coef[i] c[n - 1][i]; } dfs(0, 0); }易错点杨辉三角的预处理DFS的使用要按从小到大的顺序枚举才能保证第一个找到的是字典序最小解。剪枝条件写成cursum sum不要漏掉。