自动搬运

查看原文

来自洛谷，原作者为

	深海鱼的眼泪 **

搬运于2025-08-24 21:28:08，当前版本为作者最后更新于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;
}