$P r e s e n t$

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

先设 $p_{1}$ 表示最小的 $p$ .

当 $p_{x}$ 使用了 $p_{1}$ 次时, 可以用 $p_{x}$ 次 $p_{1}$ 替代,
举个例子, 假如当前选物品的情况是 $\sum_{i = 2}^{N} (p_{1} - 1) p_{i}$ , 此时只要在 $x \in [2, N]$ 中再选出任意一个物品 $p_{x}$ ,
则 $p_{1}$ 个 $p_{x}$ 就可以被 $p_{x}$ 个 $p_{1}$ 顶替 .

由此可以想到一个比暴力更优的背包 $d p$ 方法,
使用总容量 $\sum_{i = 1}^{N} p_{1} p_{i}$ 的背包进行 $d p$ , 然后对于每个 $a_{i}$ 的判断, 只需将 $a_{i}$ 模上 $\sum_{i = 1}^{N} p_{1} p_{i}$ (等同于 $\sum_{i = 1}^{N} p_{1} p_{i}$ 全部被 $p_{1}$ 顶替了), 此时 $a_{i}$ 一定是在背包容量内的, 直接判断即可 .

这样可以有 $60 p t s$ .

使用 $\sum_{i = 1}^{N} p_{1} p_{i}$ 为上界的原因是 $\sum_{i = 1}^{N} (p_{1} - 1) p_{i}$ 是 $p_{1}$ 不能消任何数字的极限情况, 以 $\sum_{i = 1}^{N} p_{1} p_{i}$ 为上界就可以顾及到所有的装填方法 .

思考能否以更小的背包容量解决这个问题,

设 $x = y m o d p_{1}$ , 且 $x < y$ , 则 $y - x = 0 m o d p_{1}$ ,
即对于 $m o d <mtext> </mtext> p_{1}$ 相同的 $x, y$ , 要凑成 $y$ , 可以先凑成 $x$ , 然后用 $p_{1}$ 在 $x$ 的基础上填充凑成 $y$ ,
换句话说, 若两个数模 $p_{1}$ 的值相同, 且除 $p_{1}$ 商较小的那个数字可以凑出, 则较大的那个数字也可以凑出 .
上面这句话是下方法的思想核心 .

由此可以设 $F [x]$ 表示所有满足 $i % p_{1} = x$ 且能被凑出的 $i$ 中, 最小的 $⌊ \frac{i}{p_{1}} ⌋$ ,
用类似最短路的算法转移, 最后只需检查当前数字 $a_{i}$ 是否满足条件 $F [a_{i} % p_{1}] \leq ⌊ \frac{a_{i}}{p_{1}} ⌋$ 即可 .

时间复杂度 $O (p_{1} l o g p_{1})$ .

$<mstyle mathcolor="red"> 实现部分 </mstyle>$

#include<bits/stdc++.h>
#define reg register
#define fi first
#define se second
typedef std::pair<int, int> pr;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int N;
int M;
int Ans;
int p[505];
int a[300005];
int F[200005];

int main(){
        freopen("present.in", "r", stdin);
        freopen("present.out", "w", stdout);
        N = read(), M = read();
        for(reg int i = 1; i <= N; i ++) p[i] = read();
        for(reg int i = 1; i <= M; i ++) a[i] = read();
        memset(F, 0x3f, sizeof F);
        F[0] = 0;
        std::priority_queue <pr, std::vector<pr>, std::greater<pr> > Q;
        Q.push(pr(0, 0));
        while(!Q.empty()){
                int ft = Q.top().se; Q.pop();
                for(reg int i = 2; i <= N; i ++){
                        int to = ft + p[i], cur = to%p[1];
                        if(F[cur] > F[ft] + to/p[1]){
                                F[cur] = F[ft] + to/p[1];
                                Q.push(pr(F[cur], cur));
                        }
                }
        }
        for(reg int i = 1; i <= M; i ++)
                if(F[a[i]%p[1]] <= a[i]/p[1]) Ans ++;
        printf("%d\n", Ans);
        return 0;
}

Present [神奇 背包->最短路]

P r e s e n t Present Present

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

Present [神奇背包->最短路]

$P r e s e n t$

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

$<mstyle mathcolor="red"> 实现部分 </mstyle>$