题意:给n个木棍,问能不能正好拼成一个正方形。

解法:POJ1011的简单版……不需要太多剪枝……随便剪一剪就好了……但是各种写屎来着QAQ

代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<iomanip>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1 using namespace std; int n;
int stick[25];
bool vis[25];
bool dfs(int len, int remlen, int pos, int num)
{
if(remlen == 0)
{
if(num == 3) return true;
return dfs(len, len, 0, num + 1);
}
for(int i = pos; i < n; i++)
{
if(i > 0 && !vis[i - 1] && stick[i] == stick[i - 1]) continue;
if(!vis[i] && remlen >= stick[i])
{
vis[i] = true;
if(dfs(len, remlen - stick[i], i + 1, num)) return true;
vis[i] = false;
}
if(!vis[i] && i == 0) return false;
}
return false;
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(vis, 0, sizeof vis);
scanf("%d", &n);
int sum = 0;
int maxn = 0;
for(int i = 0; i < n; i++)
{
scanf("%d", &stick[i]);
sum += stick[i];
maxn = max(maxn, stick[i]);
}
sort(stick, stick + n, cmp);
if(sum % 4 != 0 || maxn > sum / 4 || n < 4)
{
puts("no");
continue;
}
if(dfs(sum / 4, sum / 4, 0, 1)) puts("yes");
else puts("no");
}
return 0;
}

  

最新文章

  1. Maven远程仓库的认证
  2. 项目自动化建构工具gradle 入门0——环境 &amp; 废话
  3. 基于libvlc和wxWidgets的简单播放器代码阅读
  4. -canOpenURL: failed for URL: &quot;&quot; - error: &quot;(null)&quot; , iOS9 App传输安全 支持http 解决方案
  5. 自定义view
  6. Android安全问题 程序锁
  7. 用DataSet方式更新数据库表
  8. Python中单引号、双引号和三引号的区别
  9. IIS 500错误或无法显示此网页解决方法
  10. sort函数的用法与实验
  11. iOS中CocoaPods的安装及错误详解
  12. [ffmpeg] 多输入滤波同步方式(framesync)
  13. python 上台阶
  14. Sass 增强语法的样式表
  15. 操作mysql(import pymysql模块)
  16. rad 10.2
  17. Android WebView 打印 Console Log
  18. 类方法@classmethod
  19. 关于z-index这个层级的问题
  20. 关于RSU和股票期权(Stock Option)

热门文章

  1. Observer Pattern
  2. HDU4804 Campus Design 轮廓线dp
  3. JsRender系列demo(7)compline
  4. MySQL 语句级避免重复插入—— Insert Select Not Exist
  5. **【ci框架】PHP的CI框架集成Smarty的最佳方式
  6. 用django-tinymce搞个富文本编辑器
  7. lintcode: 有效的括号序列
  8. 【Linux高频命令专题(15)】more
  9. java io知识点汇总FIle类
  10. TCL语言笔记:TCL中的数组