dfs
user_8384735
c_cpp
3 years ago
2.2 kB
6
Indexable
// 307v3.cpp #include<iostream> #include<cstdio> #include<algorithm> #define N 100 using namespace std; bool isUsed[N], path[N]; int sticks[N],n; bool backtracking(int idx, int count, int now, int len); void chak(){ for (int i = 0; i < n; i++){ if (path[i]){ std::cout << sticks[i] << " "; path[i] = 0; } } std::cout << endl; } int main() { int i; while (scanf("%d", &n) && n) { int all = 0; for (i = 0; i < n; i++) { scanf("%d", &sticks[i]); all += sticks[i]; } sort(sticks, sticks + n, [](const int& a, const int& b)->bool{return a > b; }); fill(isUsed, isUsed + n, false); int len; for (len = sticks[0]; len <= all; len++) { for (int i = 0; i < n; i++) cout << (isUsed[i] == 0); cout << endl; if (all%len) continue; if (backtracking(0, 0, 0, len)) break; } printf("%d\n", len); } return 0; } bool backtracking(int idx, int count, int now, int len) { if (now == len) { //chak(); if (count == n) return true; now = 0; } if (!now) { for (idx = 0; isUsed[idx]; idx++); isUsed[idx] = path[idx] = true; if (backtracking(idx + 1, count+1, sticks[idx], len)) return true; isUsed[idx] = path[idx] = false; } else { for (int i = idx; i < n; i++) { if (isUsed[i] || (i&&sticks[i] == sticks[i - 1] && !isUsed[i - 1])) continue; if (now + sticks[i] <= len) { isUsed[i] = path[i] = true; if (backtracking(i + 1, count+1, now + sticks[i], len)) return true; isUsed[i] = path[i] = false; if (now + sticks[i] == len) return false; } } } return false; }
Editor is loading...