d965. E. 阿達的冒險
內容 ：
阿達不只是一個喜歡旅行的人，他還是一個喜歡冒險的人。最近阿達迷上了一款以冒險為主題的網頁遊戲。這款冒險遊戲很容易上手，每次只要選擇一個冒險地 點，出發之後只要等待一段時間，冒險就會結束並且得知冒險結果：獲得多少的經驗值、以及獲得哪些寶物。大地圖上的每一個冒險地點都依照了屬性分類並加以編 號，例如「高的山 14」、「深的森林 36」、「深的洞窟 28」或者是更為艱辛而困難的「挑戰者的洞窟 9」、「鍛鍊之山 33」…等等。為了避免等級較低的新手誤闖冒險地點，每一個冒險地點都會有「推薦冒險等級」，表示強烈建議這個等級的冒險者進入該地點冒險較佳。
喜歡冒險的阿達，總是想要嘗試不同的挑戰，例如當他連續進行冒險的時候，阿達會想要不斷地挑戰「推薦冒險等級」越來越高冒險地點。畢竟已經挑戰過推薦等級 X 的冒險地點以後，前往推薦等級小於或等於 X 的地點冒險就沒意思了嘛。此外，重複挑戰相同的冒險地點也是索然無味的，因此阿達也不想一直在同一個地點冒險。
人生中總是會遇到許多挫折，阿達也不例外。這天阿達想要一口氣進行很多場冒險，卻赫然發現系統壞掉了，只能讓畫面往右邊捲動！還好，只要重新登入，畫面 就會回到地圖的最左邊，又可以重新進行冒險。換句話說，若要在不重新登入的狀況下持續參與多場冒險，就只能不斷地選擇更右邊的冒險地點。為了方便起見，冒 險地點的編號由左而右一定是由小到大排好序的。雖然說重新登入以後，畫面就會回到地圖的最左邊，但是因為阿達家裡的網路不太順暢，重新登入總是會花很多很多的時間，所以他決定最多只能重新登入一次。重新開始冒險以後，第一次挑戰的冒險地點其等級可以任意選擇，不必延續前一次登入時最後冒險所推薦的冒險等級。但是，冒險過的地方無論如何都不能夠再冒險，因為阿達覺得這實在是太不冒險啦。
給出地圖中每一個冒險地點的編號以及其推薦冒險等級，請問阿達在上述條件以及自我要求之下，至多能夠進行幾場冒險呢？
輸入說明
：
第一列有一個整數 T ，代表接下來有幾組測試資料。
每一組測試資料的第一列有一個正整數 n (1 ≤ n ≤ 2000)，表示大地圖上有 n 個冒險地點。第二列有 n 個正整數 a1, a2, ..., an，其中第 i 個數 ai 表示冒險地點編號為 i 的推薦冒險等級。所有推薦冒險等級都介於 1 以及 10000 之間 (包含 1 和 10000)。
輸出說明
：
範例輸入 ：
3 5 1 2 3 4 5 5 5 4 3 2 1 7 1 3 5 8 2 6 7
範例輸出 ：
5 2 7
提示
：
出處
：
作法 : DP + BIT
DP[i][j] 代表 有一次的終點在 i, 另外一個終點在 j,
因此可以得到 DP[i][j] = max(DP[a][j] + 1 or DP[j][a] + 1) (when a < i && A[a] < A[j])
對每一個 DP[j] 建立 BIT樹, 紀錄另一個終點數值, 可以直接調查 DP[j][1~A[j]-1] 的最大值,
藉由數值離散化, 來加快運算跟減少記憶體用量
/**********************************************************************************/
/* Problem: d965 "E. 阿達的冒險" from 2010 NPSC 高中組決賽 */
/* Language: C (1475 Bytes) */
/* Result: AC(2.7s, 8.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-01 22:21:40 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2001
short C[N+1][N+1], Next[N+1], Last[N+1];
typedef struct {
int x, in;
}Sequence;
Sequence A[N];
int cmp1(const void *i, const void *j) {
Sequence *a, *b;
a = (Sequence *)i, b = (Sequence *)j;
return a->x - b->x;
}
int cmp2(const void *i, const void *j) {
Sequence *a, *b;
a = (Sequence *)i, b = (Sequence *)j;
return a->in - b->in;
}
void Modify(short *C, int n, int L, int v) {
while(n <= L) {
C[n] = C[n] > v ? C[n] : v;
n = Next[n];
}
}
int Query(short *C, int n) {
static short max;
max = 0;
while(n) {
max = max > C[n] ? max : C[n];
n = Last[n];
}
return max;
}
main() {
int T, n, i, j, tmp;
for(i = 1; i <= N; i++)
Next[i] = i+(i&(-i)), Last[i] = i-(i&(-i));
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d", &A[i].x), A[i].in = i;
A[0].x = -1, A[0].in = 0;
qsort(A, n+1, sizeof(Sequence), cmp1);
int New = 1, last = A[0].x;
for(i = 0; i <= n; i++) {
if(last != A[i].x)
last = A[i].x, New++;
A[i].x = New;
}
qsort(A, n+1, sizeof(Sequence), cmp2);
memset(C, 0, sizeof(C));
int Ans = 1;
for(i = 0; i <= n; i++) {
for(j = 0; j < i; j++) {
tmp = Query(C[j], A[i].x-1) + (i != 0);
Modify(C[i], A[j].x, New, tmp);
Modify(C[j], A[i].x, New, tmp);
Ans = Ans > tmp ? Ans : tmp;
}
}
printf("%d\n", Ans);
}
return 0;
}
上一篇：b259. H. 補習班的報名熱
下一篇：b040. E. 魔法部的任務