[TIOJ 1266] 保加利亞的俄羅斯娃娃

作法：

一開始可以想到一個 O(n^2*m^2) 的DP，從左上角開始作，dp[ i ][ j ] 是以( i , j )為終點的最常路長度，就可以花O(nm)轉移，但這複雜度非常悲劇。而如果按照數字小到大做的話，每次就變成詢問一塊從左上角開始的長方形裡面的最大值是多少，並且更新這個點的值，所以就可以寫個二維的BIT了。

code :

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=1000+10 ;
 
int n,bit[maxn][maxn] ;
 
void modify(int x,int y,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
        bit[i][j]=max(bit[i][j],val) ;
}
 
int query(int x,int y)
{
    int ret=0 ;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
        ret=max(ret,bit[i][j]) ;
    return ret ;
}
 
int x[maxn*maxn],y[maxn*maxn] ;
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
    {
        int num ; scanf("%d",&num) ;
        x[num]=i ; y[num]=j ;
    }
    for(int i=1;i<=n*n;i++)
        modify(x[i],y[i],query(x[i],y[i])+1) ;
    printf("%d\n",query(n,n)) ;
}