TIOJ::1266 . 保加利亞的俄羅斯娃娃

http://tioj.ck.tp.edu.tw/problems/1266
資料結構題。給你一個邊長為N的正方形的棋盤，每個格子裡都有一個數字，數字範圍是1~N^2，數字不會重複，問你從左上走到右下的最短路徑中，在取數字必須越取越大的限制下，你最多可以取走幾個數字。


看完題目，想一下，感覺就很DP，而且很直觀的會想到資料結構，也就是我們對每一格，想要查詢他到左上角的矩形區域內，數字比他小的那些格子的最優解。

每一格的最優解都是他到左上角之間，數字比他小的格子的最優解加一。

想要達到這種查詢，很直觀的會想到二維樹狀數組(BIT)。
我們只要把BIT的操作改成取MAX就好。

重點是DP的順序。
因為BIT只能查詢最優解，不能查詢「小於某個數字的格子」的最優解。
所以我們必須按照數字大小順序更新BIT，這樣就可以讓每次查詢都符合上面的條件。

也就是，先把每個數字的座標存起來，然後從1~N^2去更新BIT，最後答案就是(N,N)到左上角之間的最優解。

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1001;
int BIT[N][N], X[N*N],Y[N*N];
void update(int x,int y,int u,int n){
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=n;j+=j&-j){
            int&p = BIT[i][j];
            p = max(p,u);
        }
}
int query(int x,int y){
    int result = 0;
    for(int i=x;i>0;i-=i&-i)
        for(int j=y;j>0;j-=j&-j)
            result = max(result,BIT[i][j]);
    return result;
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,a;
    cin>>n;
    F(n)Fi(j,n){
        cin>>a;
        X[a] = i+1;
        Y[a] = j+1;
    }
    F(n*n)update(X[i+1], Y[i+1], query(X[i+1], Y[i+1])+1, n);
    cout<<query(n,n)<<endl;
    // while(1);
}