题解

timmark · 2023-03-31 16:14:43 · 题解

P2834 题解

题意简述：

用 n 种纸币，第 i 种的面值为 a_i 且有无限张，问凑出 w 元有多少种纸币组合。

部分分

对于 40\% 的数据，满足 n\le 10，w\le 100；

我们看到 n 和 w 都很小，那肯定爆搜啊！

code:

#include<bits/stdc++.h>
using namespace std;
int n,w,a[1005],ans;
const int mod=1e9+7;
void dfs(int step,int now,int sum){
//step表示现在使用的纸币数量，now表示使用到了第几种纸币，sum表示现在的纸币面额总和。
    if(sum>w) return ;
    if(sum==w){//得到合法答案
        ans=(ans+1)%mod;
        return ;
    }for(int i=now;i<=n;i++) dfs(step+1,i,sum+a[i]);//继续搜索
}int main(){
    cin >> n >> w ;
    for(int i=1;i<=n;i++) cin >> a[i] ;
    sort(a+1,a+n+1);//排序，纸币面额要单增
    dfs(0,1,0);
    cout << ans ;
    return 0;
}

正解做法

我们考虑怎么设计状态。

设 f_{i,j} 为只考虑前 i 种纸币来凑出 j 元的方案数。

那么考虑两种情况：

不使用第 i 种纸币，那么方案数为 f_{i-1,j}。
使用第 i 种纸币，那么先凑出 f_{i,j-a_{i}} 元，再使用 1 张第 i 种纸币。

综上，得到转移方程为：

f_{i,j}= \begin{cases} 0 & i,j\le 0\\ f_{i-1,j} & j<a_i\\ f_{i-1,j}+f_{i,j-a_i} & otherwise \end{cases}

注意取模。

code:

#include<bits/stdc++.h>
using namespace std;
int n,w,a[1005],f[1005][10005];
const int mod=1e9+7;
int main(){
    cin >> n >> w ;
    for(int i=1;i<=n;i++) cin >> a[i] ;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=w;j++){
            f[i][j]=f[i-1][j];
            if(j>=a[i]) f[i][j]=(f[i][j]+f[i][j-a[i]])%mod;
        }
    }cout << f[n][w] ;
    return 0;
}