题目见http://codeforces.com/problemset/problem/4/D
这道题是LIS（longgest increasing string）的一个变种版本。对于LIS问题，我倒是很快能写出答案，但是如果加上一些限制条件，写起来就有点难度了。
我们常用的做法是简单的dp，时间复杂度是O(n^2)，如果想要达到O(nlogn)，就要在选择最大长度上做一些优化。如下：
//返回b中刚刚大于num的元素的下标*****************************重要
int binarySearch(int num , int k )
{
int low
= 0, high = k;
= 0, high = k;
while (low
<= high)
<= high)
{
int mid
= (low + high)/2;
= (low + high)/2;
if( num >=
b[mid])
b[mid])
low = mid + 1;
else
high = mid - 1;
}
return low;
}
//非递归解，时间复杂度为O(nlgn)
//增加一个数组M[13],M[i]表示最长长度为i + 1的increasing subsequence的最后一个元素的最小值
int LIS2()
{
int k
= 1;
= 1;
b[0] = a[0];
for( int i
= 1; i < 13; i++)
= 1; i < 13; i++)
{
if(a[i]
>= b[k])
>= b[k])
b[++k] = a[i];
else
{
int pos
= binarySearch(a[i], k);
= binarySearch(a[i], k);
b[pos] = a[i];
}
}
return k;
}
这道题先对一个维度排序，这都可以想到。然后对另一个维度进行dp，注意一些限制条件，比如长宽都要大于卡片大小。用一个数组pre记录序列前一个元素的下标。
然后倒序输出pre的记录。还是要多练啊！dp太不熟了，知道了方法写出的代码还是非常烦，甚至time limited exceed，功力不够！