南京h5网站建设,织梦大气婚纱影楼网站源码 dedecms摄影工作室网站模板,如何做好网站外链,企业品牌网站设计报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周。 在QQ群上答疑#x…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周。 在QQ群上答疑 文章目录 1. DFS剪枝概述2. 剪枝例题2.1 可行性剪枝数的划分2.2 最优性剪枝、可行性剪枝生日蛋糕 2.3 可行性剪枝、记忆化搜索、DFS所有路径最长距离 2.4 搜索顺序剪枝、可行性剪枝、排除等效冗余小木棍 第13周: DFS剪枝 搜索必剪枝 无剪枝不搜索
1. DFS剪枝概述 DFS是暴力法的直接实现它把所有可能的状态都搜出来然后从中找到解。 暴力法往往比较低效因为它把时间浪费在很多不必要的计算上。 DFS能不能优化这就是剪枝。剪枝是DFS常用的优化手段常常能把指数级的复杂度优化到近似多项式的复杂度。 什么是剪枝剪枝是一个比喻把不会产生答案的、不必要的枝条“剪掉”。答案留在没有剪掉的枝条上只搜索这部分枝条就可以了从而减少搜索量提高DFS的效率。用DFS解题时大多数情况下都需要剪枝以至于可以说搜索必剪枝、无剪枝不搜索。 剪枝的关键在于剪枝的判断剪什么枝、在哪里减。DFS的剪枝技术较多有可行性剪枝、最优性剪枝、搜索顺序剪枝、排除等效冗余、记忆化搜索等等。 1可行性剪枝对当前状态进行检查如果当前条件不合法就不再继续直接返回。 2搜索顺序剪枝搜索树有多个层次和分支不同的搜索顺序会产生不同的搜索树形态复杂度也相差很大。 3最优性剪枝在最优化问题的搜索过程中如果当前花费的代价已超过前面搜索到的最优解那么本次搜索已经没有继续进行下去的意义此时停止对当前分支的搜索进行回溯。 4排除等效冗余搜索的不同分支最后的结果是一样的那么只搜一个分支就够了。 5记忆化搜索在递归的过程中有许多分支被反复计算会大大降低算法的执行效率。用记忆化搜索将已经计算出来的结果保存起来以后需要用到的时候直接取出结果避免重复运算从而提高了算法的效率。 概括剪枝的总体思想减少搜索状态。在进一步DFS之前用剪枝判断若能够剪枝则直接返回不再继续DFS。 下面用例题介绍这些剪枝方法。
2. 剪枝例题
2.1 可行性剪枝数的划分
链接数的划分 整数划分是经典问题标准解法是动态规划、母函数计算复杂度为 O ( n 2 ) O(n^2) O(n2)。当n较小时也可以用DFS暴搜出答案。
《算法竞赛》清华大学出版社494页“7.8.1 普通型母函数”介绍了整数划分的动态规划和母函数解法。 DFS求解整数划分的思路就是模拟划分的过程。由于题目不用考虑划分数的大小顺序为了简化划分过程让k份数从小到大进行。 第一个数肯定是最小的数字1 第二个数大于等于第一个数可选1、2、…最大不能超过(n-1)/(k-1)。设第2个数是x。 第三个数大于等于第二个数可选x、x1、…最大不能超过(n-1-x)/(k-2)。这个最大值的限制就是可行性剪枝。 继续以上划分过程当划分了k个数且它们的和为n时就是一个合法的划分。 C代码。代码的计算量有多大可以用变量num记录进入dfs()的次数当n200k6时答案是4132096num147123026计算量非常大。 C代码
#include bits/stdc.h
using namespace std;
int n,k,cnt;
void dfs(int x,int sum,int u){ //x:上次分的数; u:已经分了u个数; sum:前面u-1个数的和if(uk){ //已经分成了k个if(sumn) cnt; //k个加起来等于n这是一个解return;}for(int ix;sumi*(k-u)n;i) //剪枝i的最大值不超过(n-sum)/(k-u)dfs(i,sumi,u1);
}
int main(){cin nk;dfs(1,0,0); //第一个划分数是1coutcnt;
}Java代码
import java.util.Scanner;
public class Main {static int n, k, cnt;public static void dfs(int x, int sum, int u) {if (u k) {if (sum n) cnt; return;}for (int ix; sum i * (k - u) n; i) dfs(i, sum i, u 1); }public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();k scanner.nextInt();dfs(1, 0, 0);System.out.println(cnt);}
}Python代码
n, k map(int, input().split())
cnt 0
def dfs(x, sum, u): global cntif u k: if sum n: cnt 1 returnfor i in range(x, int((n - sum) / (k - u)) 1): dfs(i, sum i, u 1)
dfs(1, 0, 0)
print(cnt)2.2 最优性剪枝、可行性剪枝生日蛋糕
链接生日蛋糕 侧面积 2 π R H 2πRH 2πRH底面积 π R 2 πR^2 πR2体积 π R 2 H πR^2H πR2H。下面的讨论中忽略 π π π。 蛋糕的面积侧面积上表面面积。在下图中黑色的是上表面面积之和它等于最下面一层的底面积。设最下面一层半径是 i i i则黑色的上表面面积之和 s i × i si×i si×i。 本题用DFS枚举每一层的高度和半径并做可行性剪枝和最优性剪枝。 设最上面一层是第1层最下面一层是第m层。从第m层开始DFS。用函数dfs(k, r, h, s, v)枚举所有层当前处理到第k层第k层的半径为r高度为hs是最底层到第k层的上表面面积v是最底层到第k层的体积。并预处理数组sk[]、v[]sk[i]表示第1~第i层的最小侧面面积、vk[i]表示第1~第i层的最小体积。 1最优性剪枝1面积。记录已经得到的最小面积ans如果在DFS中得到的面积已经大于ans返回。当前处理到第k层第k层的半径是r。第k层的体积是 n − v r 2 h n-vr^2h n−vr2h得 h ( n − v ) / r 2 h(n-v)/r^2 h(n−v)/r2第k层侧面积 s c 2 r h 2 r ( n − v ) / r 2 2 ( n − v ) / r sc2rh2r(n-v)/r^22(n-v)/r sc2rh2r(n−v)/r22(n−v)/r。剪枝判断若 s c s 2 ( n − v ) / r s ≥ a n s sc s 2(n-v)/r s ≥ ans scs2(n−v)/rs≥ans返回。 2可行性剪枝2体积。如果当前已经遍历的各层的体积之和已经大于题目给定的体积n返回。剪枝判断若 v v k [ k − 1 ] n v vk[k-1] n vvk[k−1]n返回。 3可行性剪枝3半径和高度。枚举每一层的半径 i i i和高度 j j j时应该比下面一层的半径和高度小。第k-1层的体积是 i 2 h i^2h i2h它不能超过 n − v − v k [ k − 1 ] n-v-vk[k-1] n−v−vk[k−1]由 i 2 h ≤ n − v − v k [ k − 1 ] i^2h≤n-v-vk[k-1] i2h≤n−v−vk[k−1]得 h ≤ ( n − v − v k [ k − 1 ] ) / i 2 h≤(n-v-vk[k-1])/i^2 h≤(n−v−vk[k−1])/i2剪枝判断高度 j j j应该小于 ( n − v − v k [ k − 1 ] ) / i 2 (n-v-vk[k-1])/i^2 (n−v−vk[k−1])/i2。
C代码
#includebits/stdc.h
using namespace std;
const int INF0x3f3f3f3f;
int ansINF;
int sk[20],vk[20],n,m;
void dfs(int k,int r,int h,int s,int v) {//当前层、半径、高度、黑色上表面总面积、体积int MAX_h h;if(k0) { //蛋糕做完了if(vn) ansmin(ans,s); //更新表面积 return;}if(vvk[k-1] n) return; //体积n,退出。剪枝2if(2*(n-v)/rs ans) return; //侧面积黑色总面积 ans,退出。剪枝1for(int ir-1; ik; i--) { //枚举k-1层的半径ii比下一层的半径小剪枝3if(km) s i*i; //黑色总面积MAX_h min(h-1, (n-vk[k-1]-v)/i/i); //第k-1层最大的高度for(int j MAX_h; jk; j--) //枚举k-1层高度jj比下一层的高小剪枝3dfs(k-1,i,j,s2*i*j,vi*i*j);}
}
int main() {cinnm; //n:目标体积m:层数for(int i1; im; i) { // 初始化表面积和体积为最小值sk[i]sk[i-1]2*i*i; // 1~i层侧面积最小值vk[i]vk[i-1]i*i*i; // 1~i层体积最小值}dfs(m,n,n,0,0); //从最下面一层第m层开始if(ansINF) cout0;else coutans;return 0;
}Java代码
import java.util.*;
public class Main {static final int INF 0x3f3f3f3f;static int ans INF;static int[] sk;static int[] vk;static int n, m;public static void dfs(int k, int r, int h, int s, int v) {int MAX_h h;if (k 0) {if (v n) ans Math.min(ans, s);return;}if (v vk[k - 1] n) return;if (2 * (n - v) / r s ans) return;for (int i r - 1; i k; i--) {if (k m) s i * i;MAX_h Math.min(h - 1, (n - vk[k - 1] - v) / i / i);for (int j MAX_h; j k; j--)dfs(k - 1, i, j, s 2 * i * j, v i * i * j);}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();m scanner.nextInt();sk new int[m 1];vk new int[m 1];sk[0] 0;vk[0] 0;for (int i 1; i m; i) {sk[i] sk[i - 1] 2 * i * i;vk[i] vk[i - 1] i * i * i;}dfs(m, n, n, 0, 0);if (ans INF) System.out.println(0);else System.out.println(ans);scanner.close();}
}Python代码
INF 0x3f3f3f3f
ans INF
sk []
vk []
def dfs(k, r, h, s, v):global ansMAX_h hif k 0:if v n: ans min(ans, s)returnif v vk[k - 1] n: returnif 2 * (n - v) / r s ans: returnfor i in range(r - 1, k - 1, -1):if k m: s i * iMAX_h min(h - 1, (n - vk[k - 1] - v) // (i * i))for j in range(MAX_h, k - 1, -1):dfs(k - 1, i, j, s 2 * i * j, v i * i * j)
n int(input())
m int(input())
sk [0] * (m 1)
vk [0] * (m 1)
for i in range(1, m 1):sk[i] sk[i - 1] 2 * i * ivk[i] vk[i - 1] i * i * i
dfs(m, n, n, 0, 0)
if ans inf: print(0)
else: print(ans)2.3 可行性剪枝、记忆化搜索、DFS所有路径最长距离
链接最长距离 样例中移走最下面的1后最远的距离是左上角和右下角的距离等于 2 2 2 2 2.828427 \sqrt{2^22^2}2.828427 2222 2.828427。 用这道例题讲解如何用DFS搜索所有的路径。 本题的解法是图论的最短路。两个格子之间的最少障碍数量cnt就是这两个格子之间的最短路径长度。如果这条最短路径的长度满足cnt≤T那么它是一个符合题意的合法路径可以计算出这两个格子的欧氏距离。计算出任意两点的欧氏距离取最大值就是答案。 计算最短路一般用Dijkstra、SPFA这样的高级最短路算法可用于多达百万个点的图。本题的图很小也可以用DFS计算最短路虽然效率低下但是代码简单。 DFS如何计算起点s和终点t之间的最短路从s出发在每一步都向上、下、左、右四个方向继续走暴力搜索出所有到t的路径并比较得到其中最短的那条路径长度就是s、t之间的最短路。 《程序设计竞赛专题挑战教程》人民邮电出版社137页“5.1.3 DFS搜索所有路径”详细说明了如何用DFS搜索从一个起点到一个终点之间的所有路径。 用DFS计算最短路效率很低下。因为它要搜索所有路径而路径非常多其数量是指数级的。即使是很小的图只有十几个点几十条边两个点之间的路径数量也可能多达数千条。本题N和M最大等于30两点之间的路径数量可能多达百万。即使是这样小的图计算量也还是太大需要在DFS中剪枝把不可能产生答案的路径剪去。 用到两种剪枝 1可行性剪枝。从起点s出发到一个点t时如果路径上的障碍数量已经超过T个后面就不用继续了。 2记忆化搜索。从起点s出发到t的路径有很多条设第一次得到的路径长度为cnt1第二次得到的路径长度是cnt2如果cnt1cnt2那么保留cnt1就可以了第二次的路径计算的结果应该丢弃并不再从这个点继续搜索路径。 C代码。dfs(x,y,cnt)搜索和计算从起点[i, j]到任意坐标[x, y]的路径长度把最短路径长度本题中就是最少障碍数量记录在dis[x][y]中。第8行是可行性剪枝第9行是记忆化搜索。
#include bits/stdc.h
using namespace std;
int n,m,t,a[35][35];
int dis[35][35]; //dis[x,y]是起点到[x,y]的最短路就是最少障碍数
int vis[35][35]; //vis[x][y]1: 坐标[x,y]已经走过不用再走
int dx[4]{-1,1,0,0}, dy[4]{0,0,-1,1};//四个方向
void dfs(int x,int y,int cnt){ //走到坐标[x,y], 已走过的路径长度是cntcnt个障碍if(cntt) return; //可行性剪枝。已经移走了t个障碍不能再移了if(cntdis[x][y]) return; //记忆化搜索前面计算过到[x,y]的最短路dis[x][y] cnt;for(int i0;i4;i) { //向四个方向走一步int nxxdx[i], nyydy[i];if(nxn || nx1 || nym || ny1) continue; //判断越界if(vis[nx][ny]) continue; //这个点已经走过vis[nx][ny]1; //保存现场dfs(nx, ny, cnta[nx][ny]); //继续走一步vis[nx][ny]0; //恢复现场}
}
int main(){cinnmt;for(int i1;in;i)for(int j1;jm;j){ //输入网格图左上角坐标(1,1)右下角坐标(n,m)char ch; cinch; a[i][j] ch-0;}int ans0;for(int i1;in;i) //枚举任意起点[i,j]for(int j1;jm;j){memset(dis,0x3f,sizeof(dis)); //最短路长度的初值是无穷大memset(vis,0,sizeof(vis));int cnt a[i][j]1?1:0; //以[i,j]为起点dfs(i,j,cnt); //计算从起点[i,j]到任意一个点的最短路长度障碍数量for(int x1;xn;x) //计算[i,j]到任意点[x,y]的欧式距离for(int y1;ym;y)if(dis[x][y]t)ans max(ans,(x-i)*(x-i)(y-j)*(y-j)); //先不开方保证精度}printf(%.6f,sqrt(ans));
}Java代码
import java.util.*;
public class Main {static int n, m, t;static int[][] a;static int[][] dis; //dis[x,y]是起点到[x,y]的最短路就是最少障碍数static int[][] vis; //vis[x][y]1: 坐标[x,y]已经走过不用再走static int[] dx {-1, 1, 0, 0}; //四个方向static int[] dy {0, 0, -1, 1};public static void dfs(int x,int y,int cnt){ //走到[x,y], 已走过的路径长度是cntcnt个障碍if (cnt t) return; //可行性剪枝。已经移走了t个障碍不能再移了if (cnt dis[x][y]) return; //记忆化搜索前面计算过到[x,y]的最短路dis[x][y] cnt;for (int i 0; i 4; i) { //向四个方向走一步int nx x dx[i];int ny y dy[i];if (nx n || nx 1 || ny m || ny 1) continue; //判断越界if (vis[nx][ny] 1) continue; //这个点已经走过vis[nx][ny] 1; //保存现场dfs(nx, ny, cnt a[nx][ny]); //继续走一步vis[nx][ny] 0; //恢复现场}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();m scanner.nextInt();t scanner.nextInt();scanner.nextLine(); //读末尾的回车a new int[n 1][m 1];dis new int[n 1][m 1];vis new int[n 1][m 1];for (int i 1; i n; i){ //输入网格图左上角坐标(1,1)右下角坐标(n,m)String line scanner.nextLine();for (int j 1; j m; j) {char ch line.charAt(j-1);a[i][j] ch - 0;}}int ans 0;for (int i 1; i n; i) //枚举任意起点[i,j]for (int j 1; j m; j) {for (int[] row : dis) Arrays.fill(row, Integer.MAX_VALUE); //最短路初值是无穷大for (int[] row : vis) Arrays.fill(row, 0);int cnt a[i][j] 1 ? 1 : 0; //以[i,j]为起点dfs(i, j, cnt); //计算从起点[i,j]到任意一个点的最短路长度障碍数量for (int x 1; x n; x) //计算[i,j]到任意点[x,y]的欧式距离for (int y 1; y m; y)if (dis[x][y] t)ans Math.max(ans, (x-i)*(x-i)(y-j)*(y-j)); //先不开方保证精度}System.out.printf(%.6f, Math.sqrt(ans));}
}Python代码
n, m, t map(int, input().split())
a [[0] * (m1) for _ in range(n1)]
for i in range(1,n1): #输入网格图左上角坐标(1,1)右下角坐标(n,m)line input()for j in range(1,m1): a[i][j]int(line[j-1])
dis [[float(inf)] * (m1) for _ in range(n1)] #dis[x,y]是起点到[x,y]的最短路最少障碍数
vis [[0] * (m1) for _ in range(n 1)] #vis[x][y]1: 坐标[x,y]已经走过不用再走
dx [-1, 1, 0, 0] #四个方向
dy [0, 0, -1, 1]
def dfs(x, y, cnt): #走到坐标[x,y], 已走过的路径长度是cntcnt个障碍if cnt t: return #可行性剪枝。已经移走了t个障碍不能再移了if cnt dis[x][y]: return #记忆化搜索前面计算过到[x,y]的最短路dis[x][y] cntfor i in range(4): #向四个方向走一步nx x dx[i]ny y dy[i]if nxn or nx1 or nym or ny1: continue #判断越界if vis[nx][ny] 1: continue #这个点已经走过vis[nx][ny] 1 #保存现场dfs(nx, ny, cnt a[nx][ny]) #继续走一步vis[nx][ny] 0 #恢复现场
ans 0
for i in range(1, n1): #枚举任意起点[i,j]for j in range(1, m1):dis [[float(inf)] * (m1) for _ in range(n1)]vis [[0] * (m1) for _ in range(n1)]cnt 1 if a[i][j] 1 else 0 #以[i,j]为起点dfs(i, j, cnt) #计算从起点[i,j]到任意一个点的最短路长度障碍数量for x in range(1, n ): #计算[i,j]到任意点[x,y]的欧式距离for y in range(1, m1):if dis[x][y] t: ans max(ans,(x-i)**2 (y-j)**2) #先不开方保证精度
print(%.6f%(ans**0.5))2.4 搜索顺序剪枝、可行性剪枝、排除等效冗余小木棍
链接小木棍 本题是一道“DFS求全排列剪枝”的经典题。 直接的思路是猜原始木棍的长度是L然后测试n个小木棍能否拼出ksum/L根原始木棍sum是所有小木棍的总长度。可以用二分法猜这个LL的最小值是最大的aiL的最大值是65×50。由于L的范围不大也许不用二分也行。 给定一个长度L如何判断能不能拼出来下面模拟拼的过程。 在n个小木棍中选几个拼第一个L。可以用DFS求全排列的方法选小木棍。有两种可能 1在DFS求排列的过程中用几根小木棍拼出了一根L。把这几个小木棍置为已用然后对其他的小木棍继续用DFS开始新一轮的拼一根L。如果一直能拼出L而且拼出了ksum/L根那么L是一个合法的长度。 2如果在一次拼L时能用的小木棍的所有排列只能拼出一部分L失败退出下一次测试L1。 但是DFS对n个数求全排列一共有n!个全排列本题n≤65计算量极大显然会超时。如果坚持使用DFS必须剪枝。 设计以下剪枝方案。 剪枝1搜索顺序剪枝。先把小木棍从大到小排序求全排列时先选长木棍再选短木棍因为用长木棍拼比用短木棍拼更快用的木棍更少能减少枚举数这是贪心的思想。排序可以用sort()函数不过本题的ai值范围很小可以用桶排而且本题情况简单用哈希实现最简单的桶排就行优点是常数小、操作简便。 剪枝2可行性剪枝。在做某个排列时若加入某个小木棍导致长度大于L那么这个小木棍不合适。 剪枝3排除等效冗余。上面优化搜索顺序中是用贪心的策略进行搜索为什么可以用贪心因为不同顺序的拼接是等效的先拼长的x再拼短的y和先拼短y再拼长x是一样的。根据这个原理可以做进一步的剪枝这是本题最重要的剪枝。下面详细说明。 对排序后的{a1, a2, …, an}做全排列a1≥a2≥…≥an根据“DFS与排列”中给出的编码方法能够按顺序输出全排列。以{3, 2, 1}为例 第一轮的全排列a13在第一个位置得到全排列321、312。 第二轮的全排列a22在第一个位置231、213。 第三轮的全排列a31在第一个位置132、123。 回到小木棍这道题 第一轮a1位于第一个位置后面的{a2, …, an}有(n-1)!个排列。如果在这一轮的(n-1)!个排列中拼不成k个L那么不用再做第二轮、第三轮…的全排列了因为第一轮的a1和其他木棍的组合情况在第二轮、第三轮…中也会出现重复了。请读者自己证明为什么重复。 经过这个剪枝原来需要对n个数做n!次全排列现在只需要做(n-1)!次优化了n倍。 这个剪枝还可以扩展。若某个全排列的前i个拼出了L而第i-1个到第n个的排列拼不出那么对这第i-1个到第n个的排列的处理和前面讨论的一样。 剪枝4可行性剪枝。所有小木棍的sum应该是原始小木棍长度L的倍数或者说sum能整除L。 C代码
#includebits/stdc.h
using namespace std;
const int N 70 ;
int maxn0, minnN, Hash[N]; //Hash[i]:长度为i的小木棍的数量
void dfs(int k, int len, int L, int p ) { //尝试拼出k根长度都为L的小木棍if(k 0 ) { cout L; exit(0); } //已拼出k根L输出结果结束程序if(len L ) { //拼出了一根长度为L的木棍dfs(k-1, 0, L, maxn); //继续用剩下的小木棍拼长L的原始木棍应该再拼K-1根return;}for(int ip; i minn; i-- ) { //遍历每个小木棍生成排列。剪枝1if( Hash[i] i len L ) { //Hash[i]0:存在长度i的小木棍;ilenL:剪枝2Hash[i]-- ; //若Hash[i]减到0表示长度i的小木棍用完了dfs(k, leni, L, i); //继续搜下一个小木棍Hash[i]; //恢复现场这根木棍可以再用if(len 0) break; //剪枝3排除等效冗余剪枝if(leni L ) break; //剪枝3的扩展}}return;
}
int main() {int n; cin n;int sum0;while(n--) {int a; cin a;Hash[a]; //长度为a的小木棍的数量是Hash[a]sum a; //长度之和maxn max(maxn,a); //最长小木棍minn min(minn,a); //最短小木棍}for(int Lmaxn ; L sum/2 ; L ) //拼长度为L的原始木棍。枚举Lif( sum % L 0 ) //总长度能整除L说明L是一个可能的长度dfs(sum/L, 0, L, maxn); //拼长度为L的原始木棍应该有ksum/L根cout sum; //所有L都拼不出来说明原始木棍只有一根长度sumreturn 0;
}第32行从小到大枚举长度L看能否拼出长度为L的原始木棍。L的最小值是小木棍的最大值maxn最大值是sum/2表示拼2个原始木棍。第35行如果所有的L都不对那么这些小木棍只能合在一起成为一根木棍长度就是所有木棍的和sum。 函数dfs(k, len, L, p)拼k根长度为L的原始木棍如果成功就输出L并直接退出程序。参数len是拼一个L的过程中已经拼出的长度例如L7已经使用了长2、3的两根木棍此时len5还有7-52没有拼。p是现在可以用的最长小木棍。 1用桶排序对ai排序。第27行Hash[a]把a存到Hash[a]表示长度为a的小木棍的数量是Hash[a]。若Hash[i]0说明不存在长度i的小木棍。由于1≤ai≤50只需要使用Hash[1]~Hash[50]即可所以本题用桶排序非常合适。第11行i从大到小遍历Hash[i]就是对长度i从大到小排序。第11行是剪枝1。 2剪枝2可行性剪枝第12行如果i len L说明用长度i的小木棍拼会使得总长超过L不合适。 3剪枝3排除等效冗余第16行是剪枝3第17行是剪枝3的扩展这里详细解释。11行的for循环是对n个a做全排列原理见“DFS与排列”的说明。一共做n轮全排列第1轮把a1放在第一个位置、第2轮把a2放在第一个位置、…。第16行是某一轮全排列结束如果在这一轮全排列过程中得到了k个L在6行就会输出L并结束程序。如果程序能执行到第16行说明这一轮的全排列没有成功第16行就执行剪枝3并退出不再做后续轮次的全排列。如果能执行到第17行表示在某一轮的中间前面能拼出L后面拼不出此时也不再做后续轮次的全排列。 4剪枝4第33行。如果sum不能整除L表示拼不出长度为L的原始木棍。 Java代码
import java.util.*;
public class Main {static int N 70;static int maxn0, minnN;static int[] Hash new int[N];public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int sum 0;while(n-- 0) {int a sc.nextInt();Hash[a];sum a;maxn Math.max(maxn, a);minn Math.min(minn, a);}for(int L maxn; L sum / 2; L) if(sum % L 0) dfs(sum / L, 0, L, maxn); System.out.println(sum);sc.close();}public static void dfs(int k, int len, int L, int p) {if(k 0) { System.out.println(L); System.exit(0); }if(len L) {dfs(k-1, 0, L, maxn);return;}for(int i p; i minn; i--) {if(Hash[i] 0 i len L) {Hash[i]--;dfs(k, len i, L, i);Hash[i];if(len 0) break;if(len i L) break; }}return;}
}Python代码
N 70
maxn,minn 0, N
Hash [0] * N
def dfs(k, length, L, p):if k 0:print(L)exit(0)if length L:dfs(k-1, 0, L, maxn)returnfor i in range(p, minn-1, -1):if Hash[i] 0 and i length L:Hash[i] - 1dfs(k, length i, L, i)Hash[i] 1if length 0: breakif length i L: break
n int(input())
sum 0
A list(map(int, input().split()))
for i in range(n): a A[i]Hash[a] 1sum amaxn max(maxn, a)minn min(minn, a)
for L in range(maxn, sum // 2 1):if sum % L 0: dfs(sum // L, 0, L, maxn)
print(sum)
