poj-2248 Addition Chains

发表于 分类于 阅读次数： Waline： 本文字数： 134 阅读时长 ≈ 1 分钟

考点

  • DFS
  • 迭代加深

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e2 + 50;
bool vis[maxn];
int n, m, ans[maxn];

bool dfs(int dep) {
  if (dep == m) return ans[m] == n;
  int sum;
  for (int i = dep; i >= 1; --i) {
    for (int j = i; j >= 1; --j) {
      sum = ans[i] + ans[j];
      if (sum <= n && sum > ans[dep] && !vis[sum]) {
        ans[dep + 1] = sum;
        vis[sum] = 1;
        if (dfs(dep + 1)) return 1;
        vis[sum] = 0;
      }
    }
  }
  return false;
}

int main() {
  ans[1] = 1;
  while (cin >> n && n) {
    m = 1;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    while (!dfs(1)) ++m;
    for (int i = 1; i <= m; ++i) cout << ans[i] << " ";
    cout << endl;
  }
  return 0;
}

思路

直接上图。