HDU 4001 DP LIS

/*******************************************************************************
   大连网络赛的DP水题，但是当时我们队没过，其实本质跟HDU第一页的那个Monkey and Banana没啥区
别。。。一开始用栈存储，YY是普通的LIS，结果无限WA，现在想来，这题的block排完序后，也谈不上什么
单不单调的，用栈是不靠谱。。。具体解法就是先把block排下序，width从小到大，length从小到大，kind
从大到小，这样是为了保证DP时不出现无法构造Skyscraper，这个可以体会一下，然后这里可以设个哨兵，方
便后面的比较，接着就是DP了，DP数组记录的是第i个block能得到的最高的高度，然后通过比较i之前的block
就能得到最后的结果了～
*******************************************************************************/
#include <iostream>
#include <functional>
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <utility>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <limits>
#include <memory>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )
#define CLR(x, k) memset((x), (k), sizeof(x))
#define CPY(t, s) memcpy((t), (s), sizeof(s))
#define SC(t, s) static_cast<t>(s)
#define LEN(s) static_cast<int>( strlen((s)) )
#define SZ(s) static_cast<int>( (s).size() )

typedef double LF;
typedef __int64 LL;		//VC
typedef unsigned __int64 ULL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VF;
typedef vector<string> VS;

template <typename T>
T sqa(const T & x)
{
	return x * x;
}
template <typename T>
T gcd(T a, T b)
{
	if (!a || !b)
	{
		return max(a, b);
	}
	T t;
	while (t = a % b)
	{
		a = b;
		b = t;
	}
	return b;
};

const int INF_INT = 0x3f3f3f3f;
const LL INF_LL = 0x7fffffffffffffffLL;		//15f
const double oo = 10e9;
const double eps = 10e-7;
const double PI = acos(-1.0);

#define  ONLINE_JUDGE

const int MAXN = 1004;

int n;
LL dp[MAXN];
struct Node
{
	int width;
	int length;
	int thickness;
	int kind;
	Node()
	{
		CLR(this, 0);
	}
	LL area()
	{
		return SC(LL, width) * SC(LL, length);
	}
}blocks[MAXN];

bool cmp(const Node & na, const Node & nb)
{
	if (na.width != nb.width)
	{
	return na.width < nb.width;
	}
	if (na.length != nb.length)
	{
	return na.length < nb.length;
	}
	return na.kind > nb.kind;
}
bool judge(Node & pre, Node & crt)
{
	switch (crt.kind)
	{
	case 0:
		return crt.width >= pre.width && crt.length >= pre.length;
		break;
	case 1:
		return crt.width >= pre.width && crt.length >= pre.length && crt.area() > pre.area();
		break;
	case 2:
		return crt.width > pre.width && crt.length > pre.length;
		break;
	default:
		break;
	}
	return false;
}
void ace()
{
	const Node unit = Node();
	while (cin >> n, n)
	{
		for (int i = 0; i < n; ++i)
		{
			cin >> blocks[i].width >> blocks[i].length
				>> blocks[i].thickness >> blocks[i].kind;
		}
		for (int i = 0; i < n; ++i)
		{
			if (blocks[i].width > blocks[i].length)
			{
				swap(blocks[i].width, blocks[i].length);
			}
		}
		blocks[n++] = unit;		//哨兵～～～
		sort(blocks, blocks + n, cmp);
		CLR(dp, 0);
		for (int i = 1; i < n; ++i)
		{
			dp[i] = blocks[i].thickness;	//细节
			for (int j = i - 1; j >= 0; --j)
			{
				if (!judge(blocks[j], blocks[i]))
				{
					continue ;
				}
				dp[i] = max(dp[i], dp[j] + blocks[i].thickness);
			}
		}
		LL res = 0;
		for (int i = 0; i < n; ++i)
		{
			res = max(res, dp[i]);
		}
		cout << res << endl;
	}
	return ;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ace();
	return 0;
}
/*
3
10 10 12 0
10 10 12 1
10 10 11 2

2
10 10 11 1
10 10 11 1

3
4 8 1 0
4 9 2 1
5 6 4 1

2
4 8 1 0
5 7 2 0
*/