P1164 小 A 点菜——题解

解题思路

令 f[j] 表示已处理菜品中总价恰好为 $j$ 的方案数，初始 f[0]=1。每道菜从大到小更新金额：f[j]+=f[j-price]。倒序确保每份菜最多选择一次。

复杂度分析

时间复杂度 $O(NM)$，空间复杂度 $O(M)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long f[10005];
int main(){
    int n,m;cin>>n>>m;f[0]=1;
    for(int i=0;i<n;i++){int x;cin>>x;for(int j=m;j>=x;j--)f[j]+=f[j-x];}
    cout<<f[m]<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; long long f[10005]; int main(){ int n,m;cin>>n>>m;f[0]=1; for(int i=0;i<n;i++){int x;cin>>x;for(int j=m;j>=x;j--)f[j]+=f[j-x];} cout<<f[m]<<'\n';return 0; }