예제 9-2 UVa437 The Tower of Babylon(DP:DAG 중 가장 긴 길)

제목:
백서를 읽다
주요 사항:
x, y, h를 각각 높게 하면 n은 3*n종의 입방체로 전환되고 종류마다 무궁무진하기 때문에 마침 자신이 자신에게 겹치는 상황도 고려했다. 그러면 앞에 끼워 넣은 직사각형 문제로 전환하여 기억화 검색을 하면 된다.
#include
#include
#include
#include
using namespace std;
struct node
{
	int x, y, h;
}a[350*3];
bool map[350][350];
int d[350];
int n;

int dp(int i)
{
	int& ans = d[i];//   i         
	if (ans != -1)
		return ans;
	ans = a[i].h;
	for (int j = 0; j < n; j++)
		if (map[i][j])
			ans = max(ans, dp(j) + a[i].h);//                           
	return ans;
}

int main()
{
	int x, y, h,count=1;
	while (scanf("%d", &n) && n!=0)
	{
		memset(map, false, sizeof(map));
		memset(d, -1, sizeof(d));
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d%d", &x, &y, &h);//           3*n,          
			a[i].x = x; a[i].y = y; a[i].h = h;
			a[n+i].x = h; a[n + i].y = y; a[n + i].h = x;
			a[2*n+i].x = h; a[2 * n + i].y = x; a[2 * n + i].h = y;
		}
		n *= 3;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n;j++)
				if (i != j)
				{
					if (a[i].x < a[j].x&&a[i].y < a[j].y || a[i].x < a[j].y&&a[i].y < a[j].x)
						map[i][j] = true;
				}
		int ans=-1;
		for (int i = 0; i < n; i++)
			ans = max(ans, dp(i));
		printf("Case %d: maximum height = %d
", count++,ans); } return 0; }

좋은 웹페이지 즐겨찾기