pku 1011 sticks 经典DFS+剪枝

傷城~ 2022-08-18 03:10 105阅读 0赞

以前WA过的题, 今天终于把它A了.

要从这道题目中学到发现和寻找dfs的剪枝条件: 可剪之处, 无所不在.

在注释中, 我将原棒子分的各截称之为截, 将截组合成的棒子称之为棒子.有点拗口, 呵呵.

\#include <iostream> \#include <algorithm> \#include <string.h> \#include <stdio.h> using namespace std; int sticks\[64\]; int n; int sum; bool cmp(const int& a, const int& b) \{ return a > b; \} bool bOk; //ok int total; //棒子数 int length; //每条棒子的长度 bool visited\[64\]; //visit //cnt: 正在组成的第cnt根棒 //left: 正在组成的第cnt根棒剩余的长度 //startStick: 开始查询遍历的截 void dfs(int cnt, int left, int startStick) \{ if(cnt == total+1) \{ if(left == length) bOk = true; return; \} //剪枝: 当连续截相等时, 不必再搜, 直接跳过 int pre = -1; for(int i = startStick; !bOk && i < n; ++i) if(!visited\[i\] && pre != sticks\[i\] && left >= sticks\[i\]) \{ pre = sticks\[i\]; visited\[i\] = true; if(left == sticks\[i\]) dfs(cnt+1, length, 0); else dfs(cnt, left-sticks\[i\], i+1); visited\[i\] = false; if(startStick == 0) return; //剪枝: startStick=0 代表这是每个棒子的第一截,找到每条棒子的第一截时, 无需再寻找其他可能的截. //言外之意, 如果第一截还需要重新搜索, 就说明根本无法组成该长度的n个棒子.(因为这一截始终会属于某一棒子). //这也是很多程序TLE的原因: 处理无法组成该长度的棒子时,速度很慢,没有减好枝. //非常重要的剪枝条件, 你发现了吗? \} \} int main() \{ int i; while(scanf("%d", &n), n) \{ sum = 0; for(i = 0; i < n; ++i) \{ scanf("%d", &sticks\[i\]); sum += sticks\[i\]; \} sort(sticks, sticks+n, cmp); bOk = false; for(i = sticks\[0\]; i <= sum/2; ++i) \{ if(sum % i == 0) \{ memset(visited, 0, sizeof(visited)); total = sum / i; length = i; dfs(1, length, 0); if(bOk) break; \} \} printf("%d/n", bOk? i:sum); \} return 0; \}