uestc sticks

自動回転http://m.blog.csdn.net/blog/wuxinliulei/9052707
Sticks  この問題はやはり深さ優先検索＋剪定を採用します.   この問題の剪定はとても重要です.  まず、木の棒の一番短い長さを要求します.まず、木の棒の長さは一番長い棒の長さであることを明確にします.  ですから、棒の長さを読み込んだ後、一番長いものと長さの合計の2つの値を探します.  もう一つ理論的に分析した結果があります.  つまり、長い棒の柔軟性が小さいので、つなぎ合わせる時に、まず長い棒をつなぎ合わせて、短い棒を考えます.  例えば長さ8の棒をつなぎ合わせます. つぎはぎ5+3とつぎはぎ5+2+1は実は等価ですが、前者は3の利用がいいです.  データを読み込んでから棒の長さを並べ替えます.大きいから小さいまで.  そして最大の棒の長さから 配列の最初の要素から列挙を開始します.  この時もう一つの剪定があります.長さは総和の約です. これも自然です.  次は深く検索します  深度検索の終了条件は、この時も剪定されています.組み合わせられた長さ(棍棒の長さ＋1)＊長さの後、総和に等しい場合、return trueは循環して結果を出します.  次の判断は三つの場合に分けられます. 新しく加えた木の棒の長さはちょうど完全な木の棒を構成しています. まだ完全な木の棒を構成することができません.   また、細分された開始長さが0で、木の棒を完成させることができない場合、これは一つの剪定です.この場合、全部完成できないと、これを利用することは不可能です. 木の棒、そこでreturn false これはforサイクルの中の一つのreturn falseのためです.そうでなければ、forループを最後までやります.(return true以外)

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<iostream>

 6 using namespace std;

 7 #define MAX 64

 8 

 9 

10 int s[MAX], vis[MAX], n, len, sum;

11 

12 

13 bool cmp(int a, int b) 

14 {

15     return a > b;

16 }

17 

18 void input()

19 {

20     int i, j, temp;

21     sum = 0;

22     for (i = 0; i<n; i++)

23     {

24         scanf("%d ", &s[i]);

25         sum += s[i];

26     }

27     sort(s,s+n,cmp);

28 }

29 

30 

31 bool dfs(int now_len, int i, int count)

32 {

33     if ((count + 1)*len == sum)

34     {

35         return true;

36     }

37     for (int k = i; k<n; k++)

38     {

39         if (vis[k]) continue;

40         if (k&&!vis[k - 1] && s[k] == s[k - 1]) continue;

41         if (s[k] + now_len>len) continue;

42         if (now_len + s[k] == len)

43         {

44             vis[k] = 1;

45             bool result = dfs(0, 0, count + 1);

46             vis[k] = 0;

47             return result;

48         }

49         else if (now_len == 0)

50         {

51             vis[k] = 1;

52             bool result = dfs(s[k], k + 1, count);

53             vis[k] = 0;

54             return result;

55 

56 

57         }

58         else if (now_len + s[k]<len)

59         {

60             vis[k] = 1;

61             bool result = dfs(s[k] + now_len, k + 1, count);

62             vis[k] = 0;

63             if (result)

64                 return true;

65         }

66     }

67     return false;

68 }

69 int main()

70 {

71     //freopen("1.txt","r",stdin);

72     while (scanf("%d", &n) == 1 && n != 0)

73     {

74         input();

75         for (len = s[0]; len <= sum; len++)

76         {

77             if (sum%len) continue;

78             memset(vis, 0, sizeof(vis));

79             if (dfs(0, 0, 0))

80                 break;

81         }

82         printf("%d
", len);

83     }

84 }