P1705 爱与愁过火（背包）

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

多重用正序，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[][maxn];

int a[];

int m, r, n, ans;

int main(){

    cin >> m >> r >> n;

    for (int i = ; i <= m; ++i){ cin >> a[i]; V += a[i]; }

    dp[][]=;

    for (int i = ; i <= m;++i)

    for (int j = r; j >=; --j)

    for (int k = V; k >= a[i]; --k)

        dp[j][k] += dp[j - ][k - a[i]];

    for (int i = n + ; i <= V; ++i)

        ans += dp[r][i];

    cout << ans << endl;

}