codeforcesD_状压dp

题目链接：http://codeforces.com/gym/100735/problem/D
题意：给你几根木棒，每根木棒的长度已知，问最多能组成几组三角形，每根木棒只能用一次
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 int dp[10][1<<16], a[20], p[4];
17 int main()
18 {
19     int n;
20     while(~scanf("%d", &n))
21     {
22         for(int i = 1; i <= n; i++)
23             scanf("%d", &a[i]);
24         memset(dp, 0, sizeof(dp));
25         for(int i = 1; i <= n/3; i++)//最多n/3组三角形
26         {
27             for(int j = 0; j < (1<<n); j++)
28             {
29                 int te = j, k = 0;
30                 while(te)
31                 {
32                     k += te % 2;
33                     te >>= 1;
34                 }
35                 if(k != (i-1)*3)
36                     continue;
37                 for(int l1 = 0; l1 < n; l1++)//每次选三根木棒出来
38                 {
39                     int t1 = j;
40                     if(t1 & (1<<l1))
41                         continue;
42                     for(int l2 = 0; l2 < n; l2++)
43                     {
44                         int t2 = t1 | (1<<l1);
45                         if(t2 & (1<<l2))
46                             continue;
47                         for(int l3 = 0; l3 < n; l3++)
48                         {
49                             int t3 = t2 | (1<<l2);
50                             if(t3 & (1<<l3))
51                                 continue;
52                             int t4 = t3 | (1<<l3);
53                             p[0] = a[l1+1], p[1] = a[l2+1], p[2] = a[l3+1];
54                             sort(p, p+3);
55                             if(p[0]+p[1]>p[2])
56                                 dp[i][t4] = max(dp[i][t4], dp[i-1][j]+1);
57                             else
58                                 dp[i][t4] = max(dp[i][t4], dp[i-1][j]);
59                         }
60                     }
61                 }
62             }
63         }
64         int res = 0;//注意结果不是dp[n/3][1<<n]
65         for(int i = 0; i < (1<<n); i++)
66         {
67             int te = i, k = 0;
68             while(te)
69             {
70                 k += te % 2;
71                 te >>= 1;
72             }
73             if(k == (n/3)*3)
74                 res = max(res, dp[n/3][i]);
75         }
76         printf("%d
", res);
77     }
78     return 0;
79 }