글 읽기 - tree dp 질문

lyzqm 6년 전 0

3번조건을 사용했을 때는 틀리고 안했을때는 맞습니다.

3번조건을 사용할때 3차원으로 만들어서 dp를 돌렸는데 정확히 무슨이유때문인진 모르겠습니다.

(조건이 제가 생각한게 틀렸거나 3차원이다보니 par배열에 중첩이 들어가서 잘못된게 저의 뇌피셜...)

3번조건을 사용해서 맞으려면 어떻게 해야하나요?

//3번조건 O (WA)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int cost[10001];
vector<int> adj[10001];
int dp[10001][2][2];
int par[10001][2];
int solve(int here, int flag, int connect) {
	int &ret = dp[here][flag][connect];
	if (ret != -1) return ret;

	ret = 0;
	for (int next : adj[here]) {
		if (par[here] == next) continue;
		par[next] = here;
		int get = 0;
		if (flag) {		//현재 우수마을
			get = max(get, solve(next, 0, 1));
		}
		else {			//현재 우수마을이 아님
			if (connect) {	//우수마을과 연결되있음
				get = max(get, solve(next, 1, 1) + cost[next]);    //
				get = max(get, solve(next, 0, 0));
			}
			else {
				get = max(get, solve(next, 1, 1) + cost[next]);
			}
		}
		ret += get;
	}
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d", &N);
	for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);
	for (int n = 0;n < N - 1;n++) {
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	printf("%d\n", max(solve(1, 0, 0), solve(1, 1, 1) + cost[1]));
	return 0;
}


//3번조건 X (AC)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int cost[10001];
vector<int> adj[10001];
int dp[10001][2];
int par[10001];
int solve(int here, int flag) {
	int &ret = dp[here][flag];
	if (ret != -1) return ret;

	ret = 0;
	for (int &next : adj[here]) {
		if (par[here] == next) continue;
		par[next] = here;
		int get = 0;
		if (flag) {		//현재 우수마을
			get = max(get, solve(next, 0));
		}
		else {			//현재 우수마을이 아님
			get = max(get, solve(next, 1) + cost[next]);
			get = max(get, solve(next, 0));
		}
		ret += get;
	}
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d", &N);
	for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);
	for (int n = 0;n < N - 1;n++) {
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	printf("%d\n", max(solve(1, 0), solve(1, 1) + cost[1]));
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

tree dp 질문

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말