题解：P10973 Coins

chase_the_light · 2025-11-26 21:53:24 · 题解

比较模板的一道题。

遇到这样的题目，首先可以想到拆分，但是显然地，直接把每个物品拆分成 C_i 个会超时，所以考虑优化。可以发现，当我们写出所有总和不超过 C_i 且可以表示为 2^k 的形式的数，并且再加上一个值为 C_i 减去这些数的和的数，用这些数互相加就可以表示出 [1,C_i] 区间内的所有数。于是我们就可以表示出每个物品购买 [1,C_i] 个的所有情况。

于是可以获得转移方程。令 dp_j 表示是否可以用当前硬币凑出价值 j，则当我遇到一个物品时，对于每个 j，只要减去这个物品后我能够达成，这个 j 我就一定也可以获得。即 dp_j = dp_j \lor dp_{j-v_i}。

代码就很好写了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
using ll=long long;
bool dp[N];
int n,m,a[N],v[N],cnt,ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(1){
        cin>>n>>m;
        if(!(n||m)) break;
        for(int i=1;i<=n;i++) cin>>a[i];
        dp[0]=1;cnt=0;
        for(int i=1;i<=m;i++) dp[i]=0;
        for(int i=1,c;i<=n;i++){
            cin>>c;
            for(int j=1;j<=c;c-=j,j<<=1){
                v[++cnt]=j*a[i];
            }
            if(c) v[++cnt]=a[i]*c;
        }
        for(int i=1;i<=cnt;i++){
            for(int j=m;j>=v[i];j--){
                dp[j]|=dp[j-v[i]];
            }
        }
        ans=0;
        for(int i=1;i<=m;i++) ans+=dp[i];
        cout<<ans<<'\n';
    }
    return 0;
}