[ZJ][最大平均值問題] a639. DNA Density＠Morris' Blog

2013-03-15 21:40:34| 人氣943| 回應0 | 上一篇 | 下一篇

[ZJ][最大平均值問題] a639. DNA Density

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

內容： | 正體中文 (zh_TW) | ?????? ()

生物的DNA係由 A, T, C, G 四個字元所構成的序列。因為DNA的序列太長了，我們希望找出比較重要的區段，以方便研究。

生物學家對於某些含有高密度C或G的區段，特別有興趣。因此，請你撰寫程式，尋找具有最高密度C或G的區段。

假設DNA序列的最大長度為120個字元，由大、小寫英文字母ATCG組成。生物學家有興趣的DNA區段，其最小長度為L，5 ≤ L ≤ 40，該區段具有C或G的個數為w，則CG密度為 w/L。

輸入說明：

有多筆測試資料，每筆測試資料一行，包含一個整數 L 及 DNA 序列，以空白隔開。

輸出說明：

每筆測式資料，請以一行輸出其最大CG密度，並精確至小數以下第二位。

範例輸入：

5 agGCTGCAatGACAGTTGGG
20 AaggctatacagtactaatCtTtTgcatggc

範例輸出：

0.83
0.41

提示：

輸入範例說明：

一、以第一筆測資為例

L=5，表示計算CG密度的最小長度為 5 ，但最大CG密度可能出現在 L = 6, 7, 8, ...。

(1)DNA區段長度為 5，則 gGCTG、GCTGC 的CG密度皆為4/5=0.80。

(2)DNA區段長度為 6，則 gGCTGC 的CG密度為5/6=0.83。

(3)DNA區段長度 7 以上，CG密度皆小於0.83，所以最大CG密度 0.83。

二、第二筆測資：ggctatacagtactaatCtTtTgcatggc 有最大CG密度為 12/29=0.41。(此時區段長度為 29)

出處：

成大月賽 5th (管理：tarco)

轉換成 01 字串，問題等價求最大平均值問題，

最大平均值問題，使用單調&斜率優化的方式去解，
證明方式轉換成幾何問題。

效率 O(n)

證明請網路搜一下這篇論文算法合集之《浅谈数形结合思想在信息学竞赛中的应用》

/********************************************************************/
/* Problem: a639 "DNA Density" from 成大月賽 5th                    */
/* Language: C (1055 Bytes)                                        */
/* Result: AC(4ms, 329KB) judge by this@ZeroJudge                  */
/* Author: morris1028 at 2013-03-14 19:39:41                       */
/********************************************************************/

#include <stdio.h>
#include <string.h>

double get_avg(int l, int r, int sum[]) {
    return (double)(sum[r]-sum[l])/(r-l);
}
int main() {
    int L, n;
    char s[150];
    int i, j, q[150];
    while(scanf("%d %s", &L, s+1) == 2) {
        int sum[150] = {};
        n = strlen(s+1);
        for(i = 1; s[i]; i++)
            sum[i] = sum[i-1] +
            (s[i] == 'C' || s[i] == 'c' || s[i] == 'G' || s[i] == 'g');
        double ans = (double)sum[n]/n;
        int front, rear;
        front = 0, rear = -1;
        for(i = L; i <= n; i++) {
            int tmp = i-L;
            while(front < rear && get_avg(q[rear], tmp, sum) <= get_avg(q[rear-1], q[rear], sum))
                rear--;
            q[++rear] = tmp;
            while(front < rear && get_avg(q[front], i, sum) <= get_avg(q[front+1], i, sum))
                front++;
            double tans = get_avg(q[front], i, sum);
            if(tans > ans)
                ans = tans;
        }
        printf("%.2lf\n", ans + 1e-6);
    }
    return 0;
}

我要檢舉

#a639#DNA Density#最大平均值問題#斜率優化#單調

台長： Morris

您可能對以下文章有興趣

[ZJ] a586. 4. 捷運計價問題

[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢

[ZJ][LCA][offline] d767. 血緣關係

[ZJ][拓樸] a454: TOI2010 第二題：專案時程

人氣(943) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][DP] a646. 小民買糖果
此分類上一篇:[ZJ][D&C] a638. Closest-pair problem

回應(0)