CodeForcesGym 100735D Triangle Formation
2024-08-26 14:56:28
Triangle Formation
Time Limit: Unknown ms
Memory Limit: 65536KB
This problem will be judged on CodeForcesGym. Original ID: 100735D
64-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
解题:状压
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
typedef long long LL;
int dp[<<maxn],n;
LL a[maxn];
int main() {
while(~scanf("%d",&n)) {
for(int i = ; i < n; ++i) scanf("%I64d",a + i);
sort(a,a+n);
memset(dp,,sizeof dp);
int ret = ;
//cout<<"n:"<<n<<endl;
for(int i = ; i < n; ++i) {
for(int j = i + ; j < n; ++j)
for(int k = j + ; k < n; ++k) {
if(a[i] + a[j] > a[k]) {
//cout<<"ok"<<endl;
for(int t = ; t < (<<n); ++t) {
if(((t>>i)&) || ((t>>j)&) || ((t>>k)&)) continue;
int tmp = (t|(<<i)|(<<j)|(<<k));
dp[tmp] = max(dp[tmp],dp[t] + );
ret = max(ret,dp[tmp]);
}
}
}
}
printf("%d\n",ret);
}
return ;
}
最新文章
- Vue.js入门
- python头部注释 vim添加头部注释
- 《UML大战需求分析》阅读笔记06
- backBarButtonItem 替换
- 2016HUAS_ACM暑假集训2J - 今年暑假不AC
- [原创] hadoop学习笔记:卸载和安装jdk
- 制作Andriod程序的数字签名需要使用JDK
- Qt4.8.6+mingw+Qgis2.4.0基于QGis的二次开发
- jsp与Action值得对应
- 史上最坑的证书报错解决方法:Code=3000 ";未找到应用程序的“aps-environment”的权利字符串";
- SQL2012还原数据库操作在本地服务器上操作和用别的电脑远程连接到服务器进行操作的文件路径差异
- JavaScript 内存相关知识
- Head First Servlet and JSP
- 前端入门24-响应式布局(BootStrap)
- 三大家族(offset、scroll、client)
- Tex和LaTeX认识
- Java输入输出流详解
- PHP 如何自定义函数
- C++中的fstream,ifstream,oftream
- Node.js实战(四)之调试Node.js