Triangle Formation
Time Limit: Unknown ms
Memory Limit: 65536KB
This problem will be judged on CodeForcesGym. Original ID: 100735D64-bit integer IO format: %I64d Java class name: (Any)
You are given N wooden sticks. Your task is to determine how many triangles can be made from the given sticks without breaking them. Each stick can be used in at most one triangle.
Input
The first line of each test case contains the number of sticks N. (1 ≤ N ≤ 15)
The second line of each test case contains N integers leni that are the lengths of the sticks. (1 ≤ leni ≤ 109).
Output
Output single integer R – the maximal number of triangles.
Sample Input
Input
2
1 1
Output
0
Input
3
2 2 2
Output
1
Input
6
2 2 3 4 5 6
Output
2
Source
解题:状压
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 20; 4 typedef long long LL; 5 int dp[1<<maxn],n; 6 LL a[maxn]; 7 int main() { 8 while(~scanf("%d",&n)) { 9 for(int i = 0; i < n; ++i) scanf("%I64d",a + i); 10 sort(a,a+n); 11 memset(dp,0,sizeof dp); 12 int ret = 0; 13 //cout<<"n:"<<n<<endl; 14 for(int i = 0; i < n; ++i) { 15 for(int j = i + 1; j < n; ++j) 16 for(int k = j + 1; k < n; ++k) { 17 if(a[i] + a[j] > a[k]) { 18 //cout<<"ok"<<endl; 19 for(int t = 0; t < (1<<n); ++t) { 20 if(((t>>i)&1) || ((t>>j)&1) || ((t>>k)&1)) continue; 21 int tmp = (t|(1<<i)|(1<<j)|(1<<k)); 22 dp[tmp] = max(dp[tmp],dp[t] + 1); 23 ret = max(ret,dp[tmp]); 24 } 25 } 26 } 27 } 28 printf("%d ",ret); 29 } 30 return 0; 31 }