P1705 爱与愁过火（背包）

发布时间：2020-12-14 04:34:52 所属栏目：大数据来源：网络整理

导读：本来是个搜索题，但是自觉的成了背包！多重用正序，01用逆序。抽象出来一下，一个物体的体积为ai，每次装入背包需要bi（在题目中为菜数量）分钟（这个题目只是bi为 1 而已）问在r分钟内，装比n大的方案数。这是妥妥的，多条件方案01背包啊！妥妥的二维

本来是个搜索题，但是自觉的成了背包！

多重用正序，01用逆序。

抽象出来一下，一个物体的体积为ai，每次装入背包需要bi（在题目中为菜数量）分钟（这个题目只是bi为 1 而已）问在r分钟内，装比n大的方案数。

这是妥妥的，多条件方案01背包啊！妥妥的二维啊。? dp[i][j]? 表示，花了 i 分钟，装了? j 价值的东西的方案数。

#include<iostream>
using namespace std;
const int maxn = 1e4;
int V;
int dp[33][maxn];
int a[33];
int m,r,n,ans;

int main(){
    cin >> m >> r >> n;
    for (int i = 1; i <= m; ++i){ cin >> a[i]; V += a[i]; }
    dp[0][0]=1;
    for (int i = 1; i <= m;++i)
    for (int j = r; j >=1; --j)
    for (int k = V; k >= a[i]; --k)
        dp[j][k] += dp[j - 1][k - a[i]];

    for (int i = n + 1; i <= V; ++i)
        ans += dp[r][i];
    cout << ans << endl;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!