预处理,$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 ;
}

最新文章

  1. 理解CSS
  2. Enterprise Architect 学习 之 活动图
  3. MySQL 数据库设计 笔记与总结(4)维护优化
  4. 在网页中制作icon图标
  5. 利用Qemu Guest Agent (Qemu-ga) 实现 Openstack 监控平台
  6. CentOS7 service/chkconfig replace commands
  7. iOS Plugins
  8. Cobbler批量部署CentOS
  9. hihocoder 1419 重复旋律4
  10. java代码之美(7)---guava之Bimap
  11. day3-三级目录
  12. Network Monitoring in Software-Defined Networking :A Review(综述)
  13. vue分页问题参考 感谢
  14. 使用BizTalk实现RosettaNet B2B So Easy
  15. Jmeter(二十二)_脚本上传Gitlab
  16. UVM中的factory机制实现
  17. linux下去掉pdf的密码(前提:知道密码)
  18. php-laravel中间件使用
  19. 转载:resNet论文笔记
  20. php SPL四种常用的数据结构

热门文章

  1. C# 线程的定义和使用
  2. [原]OS X 10.9 Mavericks - Virtual Serial Port Issues
  3. 图解Javascript之字符串
  4. jQuery中delegate与on的用法与区别
  5. C# 操作 Excel 常见问题收集和整理
  6. enode框架step by step之消息队列的设计思路
  7. Create Table DDL sample(TSQL)
  8. PHP部分--文件上传、客户端和服务器端加限制、抓取错误信息、完整步骤
  9. .Net程序员学用Oracle系列(7):视图、函数、过程、包
  10. quagga源码分析--大内总管zebra