发表于 | 分类于

C(bitset优化dp)

给定n个重量为vi，权值为wi的物品，求能使重量和恰好为m的物品集合，其权值的异或最大值(题中所有数据范围均小于1024)

异或最大值不具有最优性传递，故用dp[i]维护异或值为i时，能得到的所有种物品集合的重量，用一个1024大小的bitset表示，dp[i][j]表示异或值为i时，是否能凑出重量为j的物品集合。而状态转移为：dp[i^w[j]]=dp[i^w[j]]|(dp[i]<<v[j])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include<bitset>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll maxn = (1<<10);
bitset<maxn> dp[maxn];
ll T, n, m;
ll v[maxn], w[maxn];
int main()
{

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (ll i = 0; i < 1024;i++)
        {
            dp[i].reset();
        }
        dp[0][0] = 1;
        for (ll i = 1; i <= n;i++)
        {
            cin >> v[i] >> w[i];
        }
        for (ll i = 1; i <= n;i++)
        {
            for (ll j = 1023; j>=0;j--)
            {
                dp[(j ^ w[i])] |= (dp[j]<<v[i]);
            }
        }
        ll ans = -1;
        for (ll i = 1023; i >= 0;i--)
        {
            if(dp[i][m]==1)
            {
                ans = i;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

复杂度分析:T(1e3+n+n1e3r+1e3),约等于1e7r(r为bitset移位一次、并一次的时间，约为bitset大小/32)

小细节:j必须从大到小遍历，否则可能出现多次选取同一物品的情况(j^w>j为什么能保证成立)