UVa437 The Tower of Babylon

好久不見！

連結：Uva437 The Tower of Babylon

題目：

給你很多種磚塊的長、寬、高，請你蓋出一座盡量高的塔。
每種提供無限多個，你可以以任意面朝下去蓋這座塔。

一個磚塊可以蓋上另一個條件為：底部的邊長必須分別小於下面那塊的長與寬。
例如長寬 (4,3) 的磚塊可以蓋在 (4,5) 之上，而 (4,6) 與 (5,6) 不可。

做法：

一種磚塊有三種不同的高，所以一開始就把他們分成三種儲存。

將所有磚塊兩兩比對，若A可以蓋在B上，就連一條有向邊，磚塊的高即為該節點的權重。

於是就形成了一張DAG，然後從入度為零的地方開始DFS，找到最長路徑就是答案了。

這是我當下寫的方法，有另一個方法是將磚塊排序後找LIS即為答案。

code:

	#include <iostream>
	#include <vector>
	#include <string.h>
	using namespace std;
	struct block {
	int len, wid;
	} arr[100];
	int W[100], in[100];
	vector<int> G[100];
	bool operator < (block x, block y) {
	return ((x.len < y.len && x.wid < y.wid) || (x.len < y.wid && x.wid < y.len));
	}
	int dfs(int x) {
	int sum = 0;
	for ( int i : G[x] )
	sum = max(sum,dfs(i));
	return W[x]+sum;
	}
	int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, a, b, c, t = 1;
	while ( cin >> n && n ) {
	int cnt = 0;
	memset(G,0,sizeof(G));
	memset(W,0,sizeof(W));
	memset(in,0,sizeof(in));
	for ( int i=0; i<n; ++i ) {
	cin >> a >> b >> c;
	W[cnt] = c; arr[cnt++] = {a,b};
	W[cnt] = b; arr[cnt++] = {a,c};
	W[cnt] = a; arr[cnt++] = {b,c};
	}
	for ( int i=0; i<cnt; ++i )
	for ( int j=0; j<cnt; ++j )
	if ( arr[i] < arr[j] ) {
	G[i].emplace_back(j);
	in[j]++;
	}
	int ans = 0;
	for ( int i=0; i<cnt; ++i )
	if ( in[i] == 0 )
	ans = max(ans,dfs(i));
	cout << "Case " << t++ << ": maximum height = " << ans << '\n';
	}
	return 0;
	}

view raw UVa437.cpp hosted with ❤ by GitHub