首页 > 代码库 > HDU 5890 Eighty seven(DP+bitset优化)
HDU 5890 Eighty seven(DP+bitset优化)
题目链接 Eighty seven
背包(用bitset预处理)然后对于每个询问O(1)回答即可。
预处理的时候背包。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for(int i(a); i <= (b); ++i) 6 #define dec(i, a, b) for(int i(a); i >= (b); --i) 7 8 const int N = 52; 9 10 int T, q, n; 11 int f[N][N][N], c[5], a[N], Q; 12 13 bitset <90> A[12]; 14 15 int check(int i, int j, int k){ 16 rep(h, 0, 10) A[h].reset(); A[0][0] = 1; 17 rep(h, 1, n) if (h != i && h != j && h != k && a[h] <= 87) dec(p, 9, 0){ 18 A[p + 1] |= A[p] << a[h]; 19 if (A[10][87]) return 1; 20 } 21 22 return 0; 23 } 24 25 int main(){ 26 27 scanf("%d", &T); 28 while (T--){ 29 scanf("%d", &n); 30 rep(i, 1, n) scanf("%d", a + i); 31 rep(i, 1, n) rep(j, i, n) rep(k, j, n) f[i][j][k] = check(i, j, k); 32 scanf("%d", &Q); 33 while (Q--){ 34 scanf("%d%d%d", c + 1, c + 2, c + 3); 35 sort(c + 1, c + 4); 36 puts(f[c[1]][c[2]][c[3]] ? "Yes" : "No"); 37 } 38 } 39 40 return 0; 41 42 }
HDU 5890 Eighty seven(DP+bitset优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。