求助,NOIOL AC,洛谷WA 60
查看原帖
求助,NOIOL AC,洛谷WA 60
51621
Altria_Pendragon_楼主2020/5/31 22:01

使用二进制优化的背包,不知道是哪里错了啊 QAQ 有好心人看看嘛

#include <bits/stdc++.h>

using namespace std;

int n, m;
int f[500010], a[210], k[210];

inline bool is_digit(char c) {
    return c <= '9' && c >= '0';
}

inline int read() {
    int tmp = 0;
    char c = getchar();
    while(!is_digit(c)) c = getchar();
    while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
    return tmp;
}

inline void write(int x) {
    if(x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}

int main() {
    n = read(), m = read();
    for(register int i = 1; i <= n; i++) {
        k[i] = read(), a[i] = read();
    }
    f[0] = 1;
    for(register int i = 1; i <= n; i++) {
        if(a[i] >= 500000 / k[i]) {
            for(register int j = k[i]; j <= m; j++) f[j] |= f[j - k[i]];
        } else {
            int L;
            for(L = 1; (1 << L) <= a[i]; L++) { 
                for(int j = 500000; j >= (1 << L - 1) * k[i]; j--) 
                    f[j] |= f[j - (1 << L - 1) * k[i]];
            }
            L--;
            for(int j = 500000; j >= (a[i] - (1 << L) + 1) * k[i]; j--)
                f[j] |= f[j - (a[i] - (1 << L) + 1) * k[i]];
        }
    }
    while(m--) {
        int qwq = read();
        if(f[qwq]) puts("Yes");
        else puts("No");
    }
    return 0;
}
2020/5/31 22:01
加载中...