[POJ 1011] Sticks【DFS】
Problem:
Time Limit: 1000MS | Memory Limit: 10000K |
Description
Input
Output
Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0
Sample Output
6 5
Source
Solution:
~~ 经典 DFS 剪枝题 ~~
从小到大枚举 [maxLen, sumLen] 上所有 sumLen 的因数,DFS 找到第一个可以拼出的长度值即可。
DFS 时尝试拼接若干根目标长度的木棍,参数仅需保存当前正在拼接的木棍长度即可(之前的木棍长度均为目标值)。
剪枝策略,缺一不可:
- 最优性剪枝:DFS 从大到小尝试,且当前木棒一定不比之前的木棒长,避免重复搜索。
- 可行性剪枝#1:如果当前木棒不可行,则相同长度的木棒均可跳过。
- 可行性剪枝#2:如果当前木棒是本次拼接的第一根,且不可行,则用更短的木棒替换一定不会更优。
- 可行性剪枝#3:如果当前木棒是本次拼接的最后一根,且不可行,则用更短的木棒替换也一定不会更优。
code: O(玄学) [164K, 16MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int n, a[70], sumlen, dest, fin; bool vis[70]; inline bool DFS(int upRange, int curlen){ // Guarantee not to search repeatedly, record current connection of sticks if(fin == n && !curlen) return 1; for(register int i = upRange; i > 0; i--){ if(vis[i] || curlen + a[i] > dest) continue; vis[i] = 1, fin++; bool isSuccessful = (curlen + a[i] == dest) ? DFS(n, 0) : DFS(i - 1, curlen + a[i]); if(isSuccessful) return 1; vis[i] = 0, fin--; if(curlen == 0) return 0; // No need to search further if it's the first stick of current connection if(curlen + a[i] == dest) return 0; // No need to search further if it's the last stick of current connection while(i > 1 && a[i - 1] == a[i]) i--; // Skip the sticks of the same length } return 0; } int main(){ while(scanf("%d", &n) != EOF && n){ sumlen = 0; for(register int i = 1; i <= n; i++) scanf("%d", a + i), sumlen += a[i]; sort(a + 1, a + n + 1); for(register int i = a[n]; i <= sumlen; i++){ if(sumlen % i) continue; // Less than 35 factors in this region dest = i, memset(vis, 0, sizeof(vis)), fin = 0; if(DFS(n, 0)){ printf("%d\n", i); break; } } } return 0; }
发表评论