基本思想使剪枝和dfs我的代码:#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int visit[70] = { 0 }, sticks[70];int sum=0,n=0,len;bool compare(int a, int b){ return a>b;}int main(){ bool dfs(int start,int snowlen,int nowlen); while (cin >> n) { if (n == 0) break; for (int i = 0; i < n; i++) { cin >> sticks[i]; sum += sticks[i]; } sort(sticks, sticks + n, compare); for (len = sticks[0]; len <= sum; len++) { if (sum%len == 0) { if (dfs(0, 0, 0)) { cout << len << endl; break; } } memset(visit, 0, sizeof(visit)); } memset(sticks, 0, sizeof(sticks)); sum = 0; } return 0;}bool dfs(int start,int snowlen, int nslen){ for (int i = start; i < n; i++) { if (snowlen + sticks[i] <= len && visit[i] == 0) { visit[i] = 1; int x,ss; x = i; ss = snowlen + sticks[i]; nslen += sticks[i]; if (snowlen + sticks[i] == len) { x = 0; ss = 0; } if (nslen == sum) return true; if (dfs(x, ss, nslen) == true) { return true; } visit[i] = 0; if (snowlen + sticks[i] == len || snowlen == 0) return false; while (sticks[i + 1] == sticks[i]) ++i; } } return false;}
目前暂无任何回答
- 0 回答
- 0 关注
- 1379 浏览
添加回答
举报
0/150
提交
取消