题目描述珅泽教育的小珅同学有n种面值不同的钱币具体地说小珅有面值w1的钱币c1个面值w2的钱币c2个面值wn的钱币cn个小珅想知道用手中的钱币恰好凑出m的方法有多少种输入第1行两个正整数nm用空格分隔第2行n个正整数w1w2⋯wn第3行n个正整数c1c2⋯cnc++代码

#include #include

using namespace std;

int main() { int n, m; cin >> n >> m;

vector<int> w(n);
vector<int> c(n);

for (int i = 0; i < n; i++) {
    cin >> w[i];
}

for (int i = 0; i < n; i++) {
    cin >> c[i];
}

vector<int> dp(m + 1, 0);
dp[0] = 1;

for (int i = 0; i < n; i++) {
    for (int j = m; j >= w[i]; j--) {
        for (int k = 1; k <= c[i] && k * w[i] <= j; k++) {
            dp[j] += dp[j - k * w[i]];
        }
    }
}

cout << dp[m] << endl;

return 0;