社区讨论

为什么背包第二层循环 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 条回复,欢迎继续交流。

正在加载回复...