HDU 5890 Eighty seven(DP+bitset优化)
2024-08-25 16:22:46
题目链接 Eighty seven
背包(用bitset预处理)然后对于每个询问O(1)回答即可。
预处理的时候背包。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i(a); i <= (b); ++i)
#define dec(i, a, b) for(int i(a); i >= (b); --i) const int N = 52; int T, q, n;
int f[N][N][N], c[5], a[N], Q; bitset <90> A[12]; int check(int i, int j, int k){
rep(h, 0, 10) A[h].reset(); A[0][0] = 1;
rep(h, 1, n) if (h != i && h != j && h != k && a[h] <= 87) dec(p, 9, 0){
A[p + 1] |= A[p] << a[h];
if (A[10][87]) return 1;
} return 0;
} int main(){ scanf("%d", &T);
while (T--){
scanf("%d", &n);
rep(i, 1, n) scanf("%d", a + i);
rep(i, 1, n) rep(j, i, n) rep(k, j, n) f[i][j][k] = check(i, j, k);
scanf("%d", &Q);
while (Q--){
scanf("%d%d%d", c + 1, c + 2, c + 3);
sort(c + 1, c + 4);
puts(f[c[1]][c[2]][c[3]] ? "Yes" : "No");
}
} return 0; }
最新文章
- 从MySQL 5.5迁移到Mariadb 10.1.14
- OPEN CASCADE Multiple Variable Function
- Android,App 常用图标尺寸规范
- GCD同步异步 串行并行大解析
- 谈谈yii2-gii如何自定义模板
- Python 元组知识点
- Oracle实现自增方式:序列+触发器
- Chart图形 [功能帮助类] Assistant创建显示图像的标签和文件 (转载)
- mongoengine连接错误:“False is not a read preference”解决方法
- POJ 3751 JAVA
- 你不可不知的Java引用类型【总结篇】
- Linux-Centos7系统下安装python2并与python3版本共存
- Dubbo服务的运行方式
- assets 与 res 目录的区别
- 【bfs】BZOJ1102- [POI2007]山峰和山谷Grz
- 算法java实现--动态规划--电路布线问题
- Python -- map, Lambda, filter and reduce
- 析构方法 deinit
- Bottle + WebUploader 修改Bottle框架从而大文件上传实现方案
- webapp 里主要的 mate 用途