首页 > 代码库 > POJ #1011 - Sticks
POJ #1011 - Sticks
This is really classic searching problem to solve. The key is pruning.
(My reference: http://blog.csdn.net/lyy289065406/article/details/6647960)
There are total 4 pruning strategies to take:
1. The target length is between max section length to total length - piece of cake
2. The target length should: totalLength % targetLength == 0 - piece of cake
3. Since there could be duplicated sections, if one of them doesn‘t work, all other sections with the same length can be skipped - piece of cake
4. At the beginning of a new search, if it doesn‘t work, we can simply skip all other following sticks - it made TLE to AC as 16ms
And yes I‘m a rookie and I learnt it by retyping:
// 1011// http://blog.csdn.net/lyy289065406/article/details/6647960#include <stdio.h>#include <stdlib.h>#include <algorithm> using namespace std;#define MAX_STICK 64bool cmp (int i,int j) { return (i > j); }bool dfs(int *sticks, bool *visited, int currLen, int tgtLen, int currInx, int usedCnt, int n){ if(usedCnt == n) return true; int skipLen = -1; for(int i = currInx; i < n; i ++ ) { if(visited[i] || sticks[i] == skipLen) continue; // Pruning 3: if that len needs to be skipped visited[i] = true; int currCmb = currLen + sticks[i]; if(currCmb < tgtLen) { if(dfs(sticks, visited, currCmb, tgtLen, i, usedCnt + 1, n)) return true; else skipLen = sticks[i]; } else if(currCmb == tgtLen) { if(dfs(sticks, visited, 0, tgtLen, 0, usedCnt + 1, n)) return true; else skipLen = sticks[i]; } visited[i] = false; if(currLen == 0) break; // Pruning 4: for starting point 0, no matches then NO // * it makes TLE passing as 16MS } return false;}int main(){ int n; while (scanf("%d", &n), n != 0) { int sticks[MAX_STICK] = { 0 }; bool visited[MAX_STICK] = { false }; // Input int sum = 0; for(int i = 0; i < n; i ++) { scanf("%d", sticks + i); sum += sticks[i]; } // Sort descending sort (sticks, sticks + n, cmp); // Searching by pruning bool bFound = false; for(int l = sticks[0]; l <= sum - l; l ++) // Pruning 1 { if( (sum % l == 0) && dfs(sticks, visited, 0, l, 0, 0, n)) // Pruning 2 { bFound = true; printf("%d\n", l); break; } } if(!bFound) printf("%d\n", sum); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。