题解 P1705 【爱与愁过火】

深海鱼的眼泪 · 2016-10-01 15:13:51 · 题解

这道题很像01背包，用 f[j,k] 保存j件物品，k元的种类，最后累加就可以了。注意 j 需要逆序（不知道为什么逆序请回顾01背包问题）。

#include <iostream>
using namespace std;
int main(){
    int m,r,n,i,a[40],f[40][3000],j,k,t=0,ans=0;
    cin>>m>>r>>n;
    for (i=1;i<=m;i++){
        cin>>a[i];
        t+=a[i];
    }
    f[0][0]=1;
    for (i=1;i<=t;i++){
        f[0][i]=0;
    }                                          //没有什么用的初始化
    for (i=1;i<=m;i++){
        for (j=r;j>=1;j--){                          //逆序枚举物品件数
            for (k=a[i];k<=t;k++){
                f[j][k]+=f[j-1][k-a[i]];
            }
        }
    }
    for (i=n+1;i<=t;i++){
        ans+=f[r][i];                       //把大于n结果都加起来
    }
    cout<<ans;
    return 0;
}