为什么-INF能AC但0会WA?
查看原帖
为什么-INF能AC但0会WA?
544520
liugh_楼主2023/12/26 18:34

我有两份代码,tarjan没写错,其他部分全部相同,只有dp的赋初值不同,为什么将取不到的dp值初始设为-INF能AC但设为0就会WA呢?求dalao解答!

dp部分如下:

// AC
int f[N][M], ind[N];
void dfs(int u) {
	for (int j = 0; j <= m; ++j) f[u][j] = (j >= C[u] ? W[u] : -INF); // 只有这里是不同点
	for (int i = Head[u]; i; i = E[i].pre) {
		int v = E[i].to;
		dfs(v);
		for (int j = m; j >= C[u]; --j) {
			for (int k = C[v]; k <= j; ++k) {
				f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
}

// WA on #2
int f[N][M], ind[N];
void dfs(int u) {
	for (int j = m; j >= C[u]; --j) f[u][j] = W[u]; // 只有这里是不同点
	for (int i = Head[u]; i; i = E[i].pre) {
		int v = E[i].to;
		dfs(v);
		for (int j = m; j >= C[u]; --j) {
			for (int k = C[v]; k <= j; ++k) {
				f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
}
2023/12/26 18:34
加载中...