AKSZ-月赛题1
2024-04-08 21:30:56
发布于：广东
15阅读
0回复
0点赞
这是一个动态规划的问题。我们可以使用一个二维数组 dp[i][j] 来记录当前选择前 i 个食物时,能量总和在 [l, r] 范围内的方案数。
算法步骤如下:
- 初始化
dp[0][0] = 1。 - 遍历每一个食物
i(从 1 到 n):- 对于每个能量值
j从l到r:- 如果
j >= w[i-1]，则dp[i][j] = dp[i-1][j-w[i-1]]。 - 否则，
dp[i][j] = dp[i-1][j]。
- 如果
- 对于每个能量值
- 最终答案就是 dp[n][r] - dp[n][l-1]。
下面是代码实现
#include <iostream>
#include <vector>
using namespace std;
int countWays(int n, int l, int r, vector<int>& w) {
int total_sum = 0;
for (int i = 0; i < n; i++) {
total_sum += w[i];
}
vector<vector<int> > dp(n + 1, vector<int>(total_sum + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= total_sum; j++) {
if (j >= w[i - 1]) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int count = 0;
for (int j = l; j <= r; j++) {
count += dp[n][j];
}
return count;
}
int main() {
int n, l, r;
cin >> n >> l >> r;
vector<int> w(n);
for (int i = 0; i < n; i++) {
cin >> w[i];
}
cout << countWays(n, l, r, w) << endl;
return 0;
}
这个算法的时间复杂度是 ，空间复杂度是 。对于给定的数据范围,这个算法可以很好地解决这个问题。
有帮助，赞一个