P1118 Backward Digit Sums G/S【洛谷算法习题】

P1118 Backward Digit Sums G/S网页链接P1118 Backward Digit Sums G/S题目描述FJ 和他的奶牛们喜欢玩一个心算游戏。他们将数字从1 11到N ( 1 ≤ N ≤ 12 ) N(1 \le N \le 12)N(1≤N≤12)按某种顺序写下来然后将相邻的数字相加得到一个数字更少的新列表。他们重复这个过程直到只剩下一个数字。例如游戏的一种情况当N 4 N4N4时可能是这样的31244367916在 FJ 背后奶牛们开始玩一个更难的游戏她们试图从最终的总和和数字N NN中确定起始序列。不幸的是这个游戏有点超出了 FJ 的心算能力。编写一个程序来帮助 FJ 玩这个游戏并跟上奶牛们的步伐。输入格式共一行两个正整数n , s u m n,sumn,sum。输出格式输出包括一行为字典序最小的那个答案。当无解的时候请什么也不输出。输入输出样例 #1输入 #14 16输出 #13 1 2 4说明/提示对于40 % 40\%40%的数据1 ≤ N ≤ 7 1\le N\le 71≤N≤7对于80 % 80\%80%的数据1 ≤ N ≤ 10 1\le N \le 101≤N≤10对于100 % 100\%100%的数据1 ≤ N ≤ 12 1\le N \le 121≤N≤121 ≤ s u m ≤ 12345 1\le sum\le 123451≤sum≤12345。由 ChatGPT 4o 翻译解题思路本题核心是杨辉三角系数转化DFS回溯剪枝求解字典序最小的数字排列。数字逐层累加的最终结果等价于初始排列每个数字乘以杨辉三角第n行对应系数的总和。先预处理杨辉三角获取权重系数采用深度优先搜索按数字从小到大枚举保证字典序最小递归过程中累加当前数字与系数的乘积若超过目标和则直接剪枝。当递归深度达到n且总和匹配目标值时输出排列并终止程序确保得到最优解。N≤12的小规模数据配合剪枝让算法效率极高。总结核心逻辑将累加问题转化为排列与杨辉三角系数的加权和通过回溯枚举合法排列。关键操作预处理杨辉三角系数DFS按序枚举数字超和剪枝找到解立即输出保证字典序最小。效率保障剪枝消除无效递归小规模数据下回溯无压力快速得到答案。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll n,q;ll a[13];ll c[13][13];//杨辉三角必备boolb[13];//判重voiddfs(ll dep,ll s){if(sq)return;if(depn){if(sq){couta[1];for(ll i2;in;i)cout a[i];exit(0);}return;}for(ll i1;in;i){if(b[i]0){b[i]1;a[dep]i;dfs(dep1,si*c[n][dep]);b[i]0;}}}intmain(){cinnq;c[1][1]1;for(ll i2;in;i)for(ll j1;ji;j)c[i][j]c[i-1][j]c[i-1][j-1];dfs(1,0);return0;}