本来是个搜索题,但是自觉的成了背包!
多重用正序,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;
}