列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[rscpp]

代碼: [選擇]

// npsc01-j1E (2001 國初 題目 E 撿石頭)
// 第1列 n 有n組資料，每一組第1列m為有m個數字(數字有可能為負) 
// 最長遞增子序列， 因 m高達 10^5又不需列出序列，故 m^2的方法不可行
// LIS nlogn , 此方法只可求長度，無法列出序列
// 參考 http://fanli7.net/a/bianchengyuyan/C__/20140524/507756.html
// 解法說明參考：http://tc.wangchao.net.cn/bbs/detail_59352.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100005];   // 存目前為止遞增列可放入的資料
int main() {
   int n, m;
// while (~scanf("%d", &n)) {  // 若資料量太大也可能需改為scanf
   cin >> n;
   while( n-- )
   {
       cin >> m;   // 每一組資料 m 個數字(有可能負數)
       int now = 0;  // 目前的長度
       cin >>a[now];  //scanf("%d", &a[now]);
       --m;   // 第1筆
       while (m--)  // 接著第2筆之後的 
       {
          int num;
          cin >> num;   //scanf("%d", &num);
          if (num > a[now]) a[++now] = num;   // 若比目前的最後一個大，加至後面
          // 否則，在a中找到 >= num 的最左一格 放入 num
          else *lower_bound(a, a + now, num) = num;
       }
       cout << now+1 << endl;  // 因由0開始 ，長度加1 //printf("%d\n", now + 1);
   }
   return 0;
}
/*
5
5
1 2 3 4 5
5
5 4 3 2 1
7
1 9 10 5 11 2 13
2
2 -1
11
1 9 10 5 6 11 7 8 2 13 14
-------------------
5
1
5
1
7
*/