POJ 1609

本文主要是介绍POJ 1609，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

开始使用DAG的DP思路解决，然而忽略一个特殊情况，两个box倘若相同尺寸，此时就不满足DAG的限制了

这道题取了一个非常巧妙的思路，因为box的l, m是固定的（也就是说不存在可以旋转的问题），这道题巧妙的利用LIS的思路解决，在学习LIS的过程中，还顺道了解了一个O(nlogn)的算法

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int maxn= 10005;
const int INF= 0x3f3f3f3f;

int n;
int dp[maxn];
pair<int, int> a[maxn];

int main(int argc, char const *argv[])
{
	while (~scanf("%d", &n) && n){
		for (int i= 0; i< n; ++i){
			scanf("%d %d", &a[i].first, &a[i].second);
		}
		sort(a, a+n);
		memset(dp, 0x3f, sizeof(dp));
		for (int i= 0; i< n; ++i){
			*upper_bound(dp, dp+n, a[i].second)= a[i].second;
		}
		printf("%d\n", (int)(lower_bound(dp, dp+n, INF)-dp));
	}
	putchar('*');
	return 0;
}

这篇关于POJ 1609的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！