a374: 5. 股票趨勢
標籤 :
通過比率 : 67% (32 人 / 48 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2012-02-13 12:44

內容

 

先生任職於證券公是一位股票分析公司經理認為目前的股票分析 軟體仍可再改進,希望彭先生再設計一套更準確的軟體。近日來,彭先生埋頭鑽 研,他發現過去的研究結果,有人提到,如果能在歷史資料中,找到與近期股票 走勢相近的樣型,即可使用此歷史樣型的交易策略,做為近期的買賣策略。為了 驗證這樣的講法是否正彭先生從股票歷史資料抽出一些特徵資並以大寫 英文字母 A~Z 代表特徵資料,因此股票資料變成一串的英文字母序列。判斷近 期股票資料與某一段歷史資料是相近,就變成判斷二串字母序列(長度不一定 ) 的相似度,亦即找出兩者的最長共同子序 (LCS longest  common subsequence)

在計算二串股票資料序列的相似時,還有一個限制,兩個相似(相同字 母)的前後間距不能太遠,否則相似度會被曲。發現了這個特性後,彭先生將 此問題正式定義為「有間距限制的最長共同子序列 (GLCS,  gapped  longest common subsequence)問題。

假設第一個序列稱為a,第二個序列稱為β。例如

a=“ACBDCAA”      β =“ADDBCDBAC” 。兩者在無間距限制的情形下, LCS   “ADCA” “ABCA”“ACBC,長度為 4。假設間距限制如下:

 

A 2, B 0, C 3, D 0

 

上述間距之意義為,如果字母 A 被選入 LCS 中,則與其前一個

 

被選入的字母之 間,在a序列最多只能有 2 個未被選入的字母,

 

β序列亦同。aβ在上述間 距限制的情形,GLCS

 

 

“ACA“ACC”,長度為 3

 

        對於無間距限制的情可將每個字母的間距視為無限本題的答案只要 輸出 GLCS 的長度即可。 

 


 

 

輸入說明
共分成二部分。第一部分,第一行為a序列,第二行為β序列,兩者都是大 寫英文字母 A~Z 的序列,每個序列長度至少為 1最長為 800第二部分自第三 行第三行有一個數值 k代表以下有 k 組測試資料(1≤k≤5)一組測試資料 為一行,每一行有多(可能零個)字母間距限制,每個限制的第一個為英文字母,第二個為間距數值(數值介於 0 400 之間)英文字母不一定按照順序,也 不一定每個字母都會出未出現的字母間距可視為無限每一行字母間距限 制的最後一個符號$,代表該(該組)的資料結束。每一行的字母間距限制情形,相鄰兩項資料之間均有一個空白隔開。
輸出說明
對於每一組測試資料,輸出它的 GLCS 輸出這 k 個值於一行,且相鄰 兩個整數之間以一個空白隔開。
範例輸入
輸入範例 1: ACBDCAA ADDBCDBAC
2
$
A 2 B 0 C 3 D 0 $

輸入範例 2: ACBDCAA ADDBCDBAC
1
C 4 A 6 $
範例輸出
輸出範例 1:

4 3

輸出範例 2:

4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 :

這題聽說可以用 N*M ><

但是我只寫出 N*M*lgN*lgM 

標籤:
出處:
100學年度全國資訊學科能力競賽 [編輯:
stanley17112000 (Stanley)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」