HDU 5808 Price List Strike Back bitset优化的背包。。水过去了

http://acm.hdu.edu.cn/showproblem.php?pid=5808

用bitset<120>dp，表示dp[0] = true，表示0出现过，dp[100] = true表示100这个数字出现过。

对于每一个新的数字，val，有转移方程，

dp = dp | (dp << val)

比如现在0000101，然后枚举了2进来，0000101 | 0010100

那个区间是暴力扫过去的，是水过去的，关键学了下bitset优化的背包。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

vector<int>vc[];

const int maxn =  + ;

int dis[maxn];

char ans[ + ];

void init() {

    for (int i = ; i <= ; ++i) vc[i].clear();

}

void work() {

    init();

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; ++i) {

        int price;

        scanf("%d", &price);

        vc[price].push_back(i);

    }

    for (int i = ; i <= n; ++i) {

        scanf("%d", &dis[i]);

    }

    for (int i = ; i <= m; ++i) {

        int L, R, mostDis, sum;

        scanf("%d%d%d%d", &L, &R, &mostDis, &sum);

        bitset<>dp;

        dp[] = ;

        bool flag = false;

        for (int j = ; j <=  && !flag; ++j) {

            if (vc[j].size() == ) continue;

            int lo = lower_bound(vc[j].begin(), vc[j].end(), L) - vc[j].begin();

            int up = upper_bound(vc[j].begin(), vc[j].end(), R) - vc[j].begin();

            up--;

            for (int k = lo; k <= up; ++k) {

                if (dis[vc[j][k]] > mostDis) continue;

                dp = dp | (dp << j);

                if (dp[sum]) {

                    flag = true;

                    break;

                }

            }

        }

        if (!flag) {

            ans[i] = '';

        } else ans[i] = '';

    }

    ans[m + ] = '\0';

    printf("%s\n", ans + );

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}