UVA Optimal Binary Search Tree(10304)

2062 단어 Binary search
제목 대의:
n개의 점과 각 점의 검색 주파수를 주고 가장 좋은 두 갈래 트리를 구축하여 두 갈래 트리의 총 권중을 최소화하고 총 권중은 각 점의 검색 주파수와 상응하는 깊이의 총계를 곱한다.3개의 점 e1, e2, e3이 설치되어 있으며 검색 빈도는 f(e1), f(e2), f(e3)이다. 만약에 구축된 두 갈래 트리 중 세 개의 점이 트리에 있는 깊이는 각각 h1, h2, h3이면 W=f(e1)*h1+f(e2)*h2+f(e3)*h3이다.문제는 가장 작은 W를 요구하는 것이다.하프만 인코딩 같아.
 
문제 해결 방법:
동적 기획은 매번 상태가 세 개의 점, 즉 뿌리 노드, 왼쪽 트리와 오른쪽 트리만 있다고 가정하고 각 노드가 뿌리 노드일 때의 최소 권중을 반복적으로 계산한다.
dp[L][H]를 설정하면 L의 첫 번째 노드에서 H의 노드까지 가장 좋은 두 갈래 나무의 최소 무게를 구성하고 뿌리 노드가 옮겨다니는 것은 L에서 H까지의 범위 내에서 옮겨다니는 것이다.상태 이동 방정식은 다음과 같습니다.
                          ans = min( ans, dp[l][k-1] + dp[k+1][h] + sum[h] - sum[l-1] - v[k] );
방정식 중 k번째 노드는 루트 노드이고 dp[l][k-1]는 l에서 k-1(즉 왼쪽 트리)의 최소 권중을 나타낸다. dp[k+1][h]는 k+1에서 h(즉 오른쪽 트리)의 최소 권중을 나타낸다. 루트 노드가 증가하면 좌우 트리의 깊이가 1을 더하기 때문에 l에서 h까지의 모든 노드의 검색 주파수를 더해야 한다. 루트 노드의 깊이가 0이기 때문에 마지막으로 k번째 노드의 검색 주파수 v[k]를 줄여야 한다.
sum[h]에 대해서는 첫 번째 노드에서 h번째 노드까지의 검색 주파수 총계를 표시하기 때문에sum[h]-sum[l-1]은 l에서 h까지의 모든 노드의 검색 주파수 총계를 나타낸다.
 
코드:
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 260

int sum[MAX];
int dp[MAX][MAX];

int main()
{
	int T, temp, h;

	while( cin>>T )
	{
		vector<int> v;
		memset( dp, 0, sizeof( dp ) );		
		memset( sum, 0, sizeof( sum ) );
		for( int i = 0; i < T; i++ )
		{
			cin>>temp;
			v.push_back(temp);
			sum[i] = sum[(i==0?0:i-1)] + temp;
		}

		for( int num = 1; num <= v.size(); num++ )  // 
		{
			for( int l = 0; l + num < v.size(); l++ )  //l  ， l + num  
			{
				h = l + num;
				int ans = 99999;
				for( int k = l; k <= h; k++ )  //  l   h  
				{
					ans = min( ans, dp[l][k-1] + dp[k+1][h] + sum[h] - sum[l-1] - v[k] );
				}
				dp[l][h] = ans;
			}
		}

		cout<<dp[0][v.size()-1]<<endl;
	}

	return 0;
}

leetcode101/검지offer28.대칭 두 갈래 나무
【bfs 대기열】102 두 갈래 나무의 층계가 두루 다니다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage