d965. E. 阿達的冒險＠Morris' Blog｜PChome Online 個人新聞台

2011-10-01 22:28:43| 人氣651| 回應0 | 上一篇 | 下一篇

d965. E. 阿達的冒險

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

　
　阿達不只是一個喜歡旅行的人，他還是一個喜歡冒險的人。最近阿達迷上了一款以冒險為主題的網頁遊戲。這款冒險遊戲很容易上手，每次只要選擇一個冒險地
點，出發之後只要等待一段時間，冒險就會結束並且得知冒險結果：獲得多少的經驗值、以及獲得哪些寶物。大地圖上的每一個冒險地點都依照了屬性分類並加以編
號，例如「高的山 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

提示：

出處：

 
  2010 NPSC 高中組決賽
  
    (管理：pcshic)

作法 : 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;
}

我要檢舉

#d965#E #阿達的冒險

台長： Morris

您可能對以下文章有興趣

b238. A. 腹黑、傲嬌

b255. D. 跑跑卡丁車

[ZJ] a361. A. 賓果遊戲

d589. B. 水之國的奇幻冒險

人氣(651) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:b040. E. 魔法部的任務
此分類上一篇:b259. H. 補習班的報名熱

回應(0)