로곡 P1040 가산점 두 갈래 나무(트리 DP, 기억화 검색)

전송문
난이도
https://www.luogu.com.cn/problem/P2014
증가 +/절약 -
이것은 트리 구조와 관련된 DP로 기억화 검색으로 해결할 수 있다.

해석에서 기호 설명

dp[][]: 동적 기획수 그룹 dp[i][j]는 정점 i에서 정점 j까지의 최대치를 나타낸다

l: 왼쪽 정점

r: 오른쪽 정점

dfs(): 귀속

분석하다.

기억화된 방식으로 검색

상태 전이 방정식이 모든 상황을 두루 훑어보고 최대치dp[l][r] = max{dfs(l, i - 1) * dfs(i + 1, r) + dp[i][i]}i의 범위는: l ≤ i ≤ r, 대응하는 path[l][r]=i

출력은 한 번의 전 순서로 반복해서 귀속시키면 실현된다

주: 본 문제의 수치 범위는 롱롱

을 사용해야 한다.

AC 코드

#include
#include

using namespace std;

const int MAXN = 35;

int path[MAXN][MAXN],nodes[MAXN];
long long dp[MAXN][MAXN];
int N;
bool first = true;


long long dfs(int l, int r) {
	if (l > r)
		return 1;
	long long totl;
	if (!dp[l][r]) {
		for (int i = l; i <= r; ++i) {
			totl = dfs(l, i - 1) * dfs(i + 1, r) + dp[i][i];
			if (totl > dp[l][r]) {
				dp[l][r] = totl;
				path[l][r] = i;
			}
		}
	}
	return dp[l][r];
}

void pri(int l,int r) {
	if (l > r)
		return;
	if (first)
		first = false;
	else
		printf(" ");
	printf("%d", path[l][r]);
	pri(l, path[l][r] - 1);
	pri(path[l][r] + 1, r);
}

int main() {

	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &dp[i][i]);
		path[i][i] = i;
	}
	cout << dfs(1, N) << endl;
	pri(1, N);
	return 0;
}