首页 > 代码库 > [HDOJ5890]Eighty seven（暴力，dp，bitset）
[HDOJ5890]Eighty seven（暴力，dp，bitset）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5890
题意：50个数，10W个询问，每次问删掉第i,j,k个数后，是否存在一种选10个数和为87的方案，只需要输出 ’Yes’ 或者 ’No’
题解：暴力：不同的询问大概2W个，每个暴力bitset DP，抠一抠能卡着过。优化1：先求出一组解，如果询问和解没交就是’Yes’，否则暴力，不同的询问大概1W个；优化2：先预处理出所有询问的答案，能方便的复用之前的DP数组，不用每次从头开始重新求。
学了一波bitset的用法，好机智，巧妙地记下了选i个数的所有可能的和的情况。
dp(i,j)表示选择i个数，j为和的种类。
dp(j)|=dp(j-1)<<a(i)。
一开始想直接背包做，发现存不下那么大的结果。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset>10 #include <vector>11 #include <deque>12 #include <queue>13 #include <stack>14 #include <ctime>15 #include <set>16 #include <map>17 #include <cmath>18 using namespace std;19 #define fr first20 #define sc second21 #define cl clear22 #define BUG puts("here!!!")23 #define W(a) while(a--)24 #define pb(a) push_back(a)25 #define Rint(a) scanf("%d", &a)26 #define Rll(a) scanf("%I64d", &a)27 #define Rs(a) scanf("%s", a)28 #define Cin(a) cin >> a29 #define FRead() freopen("in", "r", stdin)30 #define FWrite() freopen("out", "w", stdout)31 #define Rep(i, len) for(int i = 0; i < (len); i++)32 #define For(i, a, len) for(int i = (a); i < (len); i++)33 #define Cls(a) memset((a), 0, sizeof(a))34 #define Clr(a, x) memset((a), (x), sizeof(a))35 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))36 #define lrt rt << 137 #define rrt rt << 1 | 138 #define pi 3.1415926535939 #define RT return40 #define lowbit(x) x & (-x)41 #define onecnt(x) __builtin_popcount(x)42 typedef long long LL;43 typedef long double LD;44 typedef unsigned long long ULL;45 typedef pair<int, int> pii;46 typedef pair<string, int> psi;47 typedef pair<LL, LL> pll;48 typedef map<string, int> msi;49 typedef vector<int> vi;50 typedef vector<LL> vl;51 typedef vector<vl> vvl;52 typedef vector<bool> vb;53 54 const int maxn = 55;55 int n;56 int a[maxn];57 bool sta[maxn][maxn][maxn];58 bitset<88> dp[11];59 60 bool ok(int x, int y, int z) {61 Rep(i, 11) dp[i].reset();62 dp[0][0] = 1;63 For(i, 1, n+1) {64 if(i == x || i == y || i == z || a[i] > 87) continue;65 for(int j = 10; j >= 1; j--) {66 dp[j] |= dp[j-1] << a[i];67 }68 }69 return dp[10][87];70 }71 72 signed main() {73 //FRead();74 int T, q, x[5];75 Rint(T);76 W(T) {77 Rint(n);78 For(i, 1, n+1) Rint(a[i]);79 For(i, 1, n+1) {80 For(j, i, n+1) {81 For(k, j, n+1) {82 sta[i][j][k] = ok(i, j, k);83 }84 }85 }86 Rint(q);87 W(q) {88 Rep(i, 3) Rint(x[i]);89 sort(x, x+3);90 if(sta[x[0]][x[1]][x[2]]) puts("Yes");91 else puts("No");92 }93 }94 RT 0;95 }
[HDOJ5890]Eighty seven（暴力，dp，bitset）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。