本文主要是介绍POJ 1011--Sticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：这是题目
题意：给你一些切断了的木棍，求原木棍的长度，长度尽可能小，数目不限。
思路：爆搜，但是会T，要有一些处理。
1. 木棍从大到小排序，因为你总是要把长的和短的先拼凑的，相同的木棍如果一根不行，那后面相同的也肯定不行。
2. 要拼凑当前的木块肯定是从它后面的木棍开始找，因为如果这个木棍没有被拼凑那么它肯定是因为前面的用不到它，所以只要从它后面的木棍开始找
3. 如果一个木棍和前一个木棍刚好凑成，但是搜到最后发现不行，那么不用搜下去，肯定拼不成，因为如果要拼9，有6和3正好拼成，但是搜到最后不行，还有2和1，那么2和1也肯定不行，因为想想，2和1比3灵活，留着灵活的都拼不了，那么肯定不行。
4. 如果从当前搜的木棍开始，发现没有木棍能和这个木棍拼凑，那么肯定不行，因为想一想，这个木棍肯定会多出来。
好了，以上剪枝之后就不会TLE了。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;const int MAX = 100;
int ss[MAX];
int stick[MAX];
bool visit[MAX];
int n, ma, sum, num, l;bool dfs(int s, int len, int pos) {bool sign = (len == 0?true:false);if (s == num) {return true;}for (int i = pos + 1; i < n; i++) {//从当前木棍的后一个木棍开始搜，会TLE的第2种情况if (visit[i]) continue;if (len + stick[i] == l) {visit[i] = true;if (dfs(s+1, 0, -1)) {return true;}//正好凑成一块，从最前面开始搜visit[i] = false;return false;//会TLE的第3种情况，见上面的思路}else if(len + stick[i] < l) {visit[i] = true;if (dfs(s, len + stick[i], i)) {return true;}visit[i] = false;if (sign) return false;//会TLE的第4种情况，前面多出来了，凑不成while(stick[i] == stick[i+1]) i++;//会TLE的第1种情况，相同的木棍有一个不行，那么都不行}}return false;
}int main() {while(scanf("%d", &n) != EOF) {memset(visit, false, sizeof(visit));ma = 0;sum = 0;if (n == 0)break;for (int i = 0; i < n; i++) {scanf("%d", &ss[i]);if (ma < ss[i]) {ma = ss[i];}sum += ss[i];}sort(ss, ss+n);int k = 0;for (int i = n-1; i >= 0; i--)stick[k++] = ss[i];for (l = ma; l <= sum; l++) {if (sum % l != 0)//总长度一定是每根的倍数continue;else {num = sum / l;//能够拼成的原木棍数目if(dfs(0, 0, -1)) {printf("%d\n", l);break;}}}}return 0;
}这篇关于POJ 1011--Sticks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
