hdu5890 暴力DP（bitset常数优化）
题目连接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5890
这道题目我的队友当场暴力搜索写过，ORZ。赛后发现是bitset优化的DP，因为之前没写过这样的DP，所以记录一下。其实暴力的DP很好写，不过算一下复杂度，本质不同的询问有2W左右，可以开数组记录一下，每次暴力DP的代价是87*10*47*47大概4W左右，总复杂度8e8，一般是跑不过的。但是常数优化很强大有木有？何况bitset是自带的stl，用起来很方便。因为状态只有01两种，所以直接用bitset存储，状态转移的时候没加一个数，87个状态整体左移这个数的大小即可，复杂度为8e8/w，w据说是机器字长，w=8位左右正好可以卡过。还有其他优化方法本渣渣就不在介绍了，可以上X姐博客上看。
附上代码：
//#include <bits\stdc++.h>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <bitset> #define sqr(x) ((x)*(x))
#define lson (p<<1)
#define rson (lson | 1)
#define EPS 1e-10
#define PII pair<int,int>
#define PLI pair<LL,int>
#define PLL pair<LL,LL>
#define PIL pair<int,LL>
#define mk(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
#define FR freopen("in.txt","r",stdin)
#define FW freopen("out.txt","w",stdout)
using namespace std;
template <class T>
inline void read(T &x){char c = getchar(); x = 0;while(!isdigit(c))c = getchar();while(isdigit(c)){x=x*10 + c-'0';c = getchar();}}
template <class T>
inline void rd(T &res) {static char ch; bool sgn = false;while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;res = ch - 48;while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48; res = sgn ? -res : res;}
template <class T> void Out(T a) { if(a < 0){putchar('-');a = -a;}if(a >= 10)Out(a / 10);putchar(a % 10 + '0'); }
typedef long long LL;
const int N = 12;
const int M = 51;
bitset<88>bi[N];
int ans[M][M][M],a[M],b[4];
bool flag[M];
int main()
{ int cas;rd(cas);while(cas--){int n,m;rd(n);for(int i=1;i<=n;i++) rd(a[i]);memset(ans,-1,sizeof(ans));rd(m);while(m--){for(int i=0;i<3;i++) rd(b[i]);sort(b,b+3);if(ans[b[0]][b[1]][b[2]] != -1){if(ans[b[0]][b[1]][b[2]]) puts("Yes");else puts("No");continue;} for(int i=0;i<3;i++) flag[b[i] ] = 1;for(int i=0;i<=10;i++) bi[i].reset();bi[0][0] = 1;for(int i=1;i<=n;i++){if(flag[i] || a[i]>87) continue;for(int j=9;j>=0;j--){bi[j+1] |= (bi[j] << a[i]);}} ans[b[0]][b[1]][b[2]] = bi[10][87];if(bi[10][87]) puts("Yes"); else puts("No"); for(int i=0;i<3;i++) flag[b[i] ] = 0;}}return 0;
}
