HDU 5890 Eighty seven
2024-08-24 13:23:53
预处理,$01$背包,$bitset$优化。
可以预处理出每一种询问的答案,用$01$背包计算答案,$dp[i][j][k]$表示,前$i$个数字中,选择了$j$个,能否凑出$k$这个数字,可以开成$bitset<90>dp[55][12]$,第三维$bitset$位运算优化。
$HDU$不稳,有时超时,有时通过。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*+c-''; c=getchar();}
} const int maxn=;
int T,n,s[];
bool f[maxn][maxn][maxn],g[maxn][maxn][maxn]; bool get(int a,int b,int c)
{
bitset<>dp[maxn][]; int p[], sz=;
for(int i=;i<=n;i++)
{
if(s[i]>) continue;
if(i==a) continue;
if(i==b) continue;
if(i==c) continue;
p[sz++]=s[i];
} if(sz==) return ; dp[][][p[]]=;
for(int i=;i<sz;i++)
{
dp[i][]|=dp[i-][]; dp[i][][p[i]]=;
for(int j=;j<=;j++)
{
dp[i][j]|=dp[i-][j];
dp[i][j]|=dp[i-][j-]<<p[i];
}
if(dp[i][][]==) return ;
}
return ;
} int main()
{
scanf("%d",&T);
for(int i=;i<=T;i++)
{
memset(f,,sizeof f);
memset(g,,sizeof g); scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&s[i]); int Q; scanf("%d",&Q);
while(Q--)
{
int op[]; scanf("%d%d%d",&op[],&op[],&op[]);
sort(op,op+); if(g[op[]][op[]][op[]])
{
if(f[op[]][op[]][op[]]==)printf("No\n");
else printf("Yes\n");
}
else
{
f[op[]][op[]][op[]]=get(op[],op[],op[]);
if(f[op[]][op[]][op[]]==)printf("No\n");
else printf("Yes\n");
g[op[]][op[]][op[]]=;
}
}
}
return ;
}
最新文章
- 理解CSS
- Enterprise Architect 学习 之 活动图
- MySQL 数据库设计 笔记与总结(4)维护优化
- 在网页中制作icon图标
- 利用Qemu Guest Agent (Qemu-ga) 实现 Openstack 监控平台
- CentOS7 service/chkconfig replace commands
- iOS Plugins
- Cobbler批量部署CentOS
- hihocoder 1419 重复旋律4
- java代码之美(7)---guava之Bimap
- day3-三级目录
- Network Monitoring in Software-Defined Networking :A Review(综述)
- vue分页问题参考 感谢
- 使用BizTalk实现RosettaNet B2B So Easy
- Jmeter(二十二)_脚本上传Gitlab
- UVM中的factory机制实现
- linux下去掉pdf的密码(前提:知道密码)
- php-laravel中间件使用
- 转载:resNet论文笔记
- php SPL四种常用的数据结构
热门文章
- C# 线程的定义和使用
- [原]OS X 10.9 Mavericks - Virtual Serial Port Issues
- 图解Javascript之字符串
- jQuery中delegate与on的用法与区别
- C# 操作 Excel 常见问题收集和整理
- enode框架step by step之消息队列的设计思路
- Create Table DDL sample(TSQL)
- PHP部分--文件上传、客户端和服务器端加限制、抓取错误信息、完整步骤
- .Net程序员学用Oracle系列(7):视图、函数、过程、包
- quagga源码分析--大内总管zebra