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)到左上角之間的最優解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #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;
}
|
