nlogn的最长不上升子序列

nlogn的最长不上升子序列虽然不难,也很常用,但是很容易打错,一不注意就把变量名打错了.

主要思想是用二分优化"寻找a[j]>=a[i]中f[j]最大的j"

for(int i = 1;i <= N;i++)
{
    int maxx = -INF;
    for(int j = 1;j < i;j++)//优化这个循环
    {
        if(a[j] >= a[i])maxx = max(maxx,f[j]);
    }
    f[i] = (maxx == INF)?1:maxx+1;
}

既然使用二分,就要寻找一个有单调性的东西.

#P1004 方格取数

题目描述

设有N*N*的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）：