DDOSvoid's Blog

Luogu P3092 [USACO13NOV]No Change G

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3092

状压dp练习

Solution

容易想到dp的状态只需要存储当前用掉的硬币所能买的最多物品

加一枚新硬币时所能到达的右端点二分即可

时间复杂度 $O(2^k k logn)$

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
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100010
#define maxm 17
#define ll long long 
using namespace std;

int n, m, a[maxn], b[maxm]; ll s[maxn]; 

int f[1 << maxm];

int calc(int x, int v) {
    int l = x + 1, r = n, mid, ans = x;
    while (l <= r) {
        mid = l + r >> 1;
        if (v >= s[mid] - s[x]) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
} 

int main() {
    cin >> m >> n; int M = (1 << m) - 1; 
    for (int i = 1; i <= m; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
    for (int S = 0; S < M; ++S) 
        for (int i = 1; i <= m; ++i) {
            int T = S | 1 << i - 1; if (S == T) continue;
            f[T] = max(f[T], calc(f[S], b[i]));
        }
    int ans = -1;
    for (int i = 1; i <= M; ++i) {
        if (f[i] != n) continue;
        int res = 0;
        for (int j = 1; j <= m; ++j)
            if (!(i >> j - 1 & 1)) res += b[j]; 
        ans = max(ans, res);
    } cout << ans << endl; 
    return 0;
}