社区讨论
为什么背包第二层循环 j 从 m 到 0 或 1 都可以 AC?
P1757通天之分组背包参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo19hh7z
- 此快照首次捕获于
- 2023/10/22 17:23 2 年前
- 此快照最后确认于
- 2023/11/02 17:25 2 年前
rt
CPP#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10003;
vector<int> G[103];
int a[N], b[N], f[N];
int main()
{
int m, n, t = 0;
scanf("%d%d", &m, &n);
for(int i = 1; i <= 101; ++i)
G[i].push_back(-1);
for(int i = 1; i <= n; ++i)
{
int c;
scanf("%d%d%d", &a[i], &b[i], &c);
t = max(t, c);
G[c].push_back(i);
}
for(int i = 1; i <= t; ++i)
for(int j = m; j >= 0; --j) //为什么 0 或 1 都可以 AC?
{
int len = G[i].size() - 1;
for(int k = 1; k <= len; ++k)
if(j >= a[G[i][k]])
f[j] = max(f[j], f[j - a[G[i][k]]] + b[G[i][k]]);
}
printf("%d", f[m]);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...