首页 > 代码库 > [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)