NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 A.蜜蜂的約會

作者 主題: NPSC 2008 高中組 決賽 A.蜜蜂的約會  (閱讀 2678 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2008 高中組 決賽 A.蜜蜂的約會
« 於: 十一月 30, 2009, 01:58:02 pm »

NPSC 2008 高中組 決賽 A.蜜蜂的約會

說明:給你兩個數列,請你找出最長共同子序列(Longest Common Sequence)的長度。

解法:最長共同子序列(Longest Common Sequence,簡稱 LCS)是DP 的經典題目之一,詳細原理可參考「DJWS的網路日誌」 http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html 的說明,這邊只要建一個 (N+1)(N+1) 的表格,T[0][X] 和 T[X][0] 全部歸零,而 T[ i ][j] 代表 A 數列前 i 個元素和 B 數列前 j 個元素之 LCS 長度(元素從1開始編號),當 A 的第 i 個元素和 B 的第 j 個元素相等時,它會等於左上角那格的數值加一,也就是 T[ i ][j]=T[i-1][j-1]+1,而當 A 的第 i 個元素和 B 的第 j 個元素不相等時,它則是上面那格和左邊那格中比較大的那個,也就是 T[ i ][j]=max(T[i-1][j], T[ i ][j-1])。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 A - 蜜蜂的約會
// By sagit at TCGS
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const short int MAX=10002;
short int Table[MAX][MAX]={0}, A[MAX], B[MAX];

int main()
{
    freopen("pa.in", "rt", stdin);
    freopen("pa.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, i, j;
    while (1)
    {
        cin >> n;
        if ( cin.fail() ) break;
        if ( n>=MAX ) break;
        for (i=1; i<=n; i++) cin >> A[i];
        for (i=1; i<=n; i++) cin >> B[i];
        for (i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                Table[i][j] = (A[i]==B[j]) ? Table[i-1][j-1]+1 :
                              max(Table[i-1][j], Table[i][j-1]);
        cout << Table[n][n] << endl;
    }
//    system("PAUSE");
    return 0;
}
« 上次編輯: 十一月 30, 2009, 02:02:03 pm 由 sagit »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
O(nlogn) 修正版
« 回覆 #1 於: 十一月 30, 2009, 02:04:59 pm »

感謝 TLE、su_horng 等網友提供解法與指正。

修正原因:本題原本解法之時間複雜度為O(n^2),但比賽中測資改為N最大為10^5,原本的解法會超過時間,故需要更快的解法。

解法:找出數列二的數字在數列一裡出現的順序,再對這個順序以最長遞增子序列(Longest Increasing Subsequence, LIS)的 O(nlogn)解法來處理,即可得到答案,此解法可參考「DJWS的網路日誌」 http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html 之說明。

首先,我們不記錄第一個數列的數字為何,改成記錄各數字出現的順序是第幾個,這樣要從第二個數列找出它在第一個數列的位置時,可以直接查表得知,不用再逐一搜尋。接下來,我們利用 LIS 陣列記錄當長度為 n 時的最小元素,這個陣列會是遞增的,如果新來的數字比最後一個元素大,則將它新增到到 LIS 陣列的後面,並把大小加一。而如果新來的數字比最後一個元素小,則以二元搜尋法尋找大於它的最小元素,把該元素換成它即可。而最後 LIS 陣列元素的個數,即是我們要的答案。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 A - 蜜蜂的約會
// By sagit at TCGS
#include <cstdlib>
#include <iostream>

using namespace std;

const int MAX=100001;
// Pos[k] 記錄數字 k 在第一個數列中出現的順序
// LIS[n] 記錄 LIS 為 n 的最小元素, Len 記錄目前 LIS 的最大值
int Pos[MAX], LIS[MAX], Len;

int main()
{
    freopen("pa.in", "rt", stdin);
    freopen("pa.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, i, j, a, first, last, middle;
    while (1)
    {
        cin >> n;
        if ( cin.fail() ) break;
        for (i=0; i<n; i++)             // 輸入第一個數列
        {
            cin >> a;
            Pos[a]=i;                   // 記錄該數字在數列中出現的順序
        }
        cin >> a;                       // 處理第二個數列的第一個數
        LIS[0]=Pos[a];
        Len=0;
        for (i=1; i<n; i++)
        {
            cin >> a;
            a=Pos[a];                   // 將數字轉換成第一個數列中出現的順序
            if (a>LIS[Len])             // 如果比最後一個數還要大
                LIS[++Len]=a;
            else
            {
                first=0, last=Len;
                while (first<=last)      // Binary Search
                {
                    middle=(last+first)/2;
                    if (LIS[middle]>a) last=middle-1;
                    else if (LIS[middle]<a) first=middle+1;
                    else break;
                }
                if (LIS[middle]<a) LIS[middle+1]=a;
                else LIS[middle]=a;
            }
        }
        cout << Len+1 << endl;
    }
//    system("PAUSE");
    return 0;
}
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 A.蜜蜂的約會
« 回覆 #2 於: 十一月 30, 2009, 08:09:39 pm »

老師,對了,LCS直接開 O(n^2) 的空間在 OJ 上有可能 MLE,可能會需要滾動XD。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 A.蜜蜂的約會
« 回覆 #3 於: 十一月 30, 2009, 11:25:16 pm »

感謝補充, ZeroJudge 的預設值是 64MB,
很多題目(特別是Graph的)測資大一點的就爆了,
我還遇過用內建STL裡的list或deque不行,
要自己寫Linked-List才會過的情況,
所以我是不太想理它,
在自己的電腦上能過就好....

是說, NPSC的題目這兩年來有越來越難的傾向.... XD
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 A.蜜蜂的約會