APIO 2008デオキシリボヌクレオチドDNA

に言及
DNA配列のような生命科学データの解析はコンピュータの興味深い応用である.生物学的に言えば、DNAはアデニン、セピリジン、グアニン、胸腺ピリジンの4つのヌクレオチドからなる鎖構造である.これら4種類のヌクレオチドは、それぞれ大文字A、C、G、Tで表される.このように、1つのDNA単鎖は、以上の4つの文字のみを含む文字列として表すことができる.このような文字列をDNA配列と呼ぶ.ジルコニウムは、生物学者がDNA単鎖中のいくつかのヌクレオチドを特定できない場合がある.この場合、文字Nは不確定なヌクレオチドを表すために使用される.言い換えれば、Nは、A、C、G、Tのいずれかの文字を表すために使用され得る.1つ以上のNを含むDNA配列を未完成配列と呼ぶ.逆に、完了シーケンスと呼ばれます.1つの完了シーケンスが、1つの未完了シーケンスの各Nを任意にA、C、G、Tに置き換えることによって得られる場合、完了シーケンスは、この未完了シーケンスに適していると称される.例えば、ACCCTはACNNTに適しているが、AGGATは適していない. 研究者たちは、AがCより優先され、CがGより優先され、GがTより優先される4種類のヌクレオチドをよく並べ替えている.1つのDNA配列中の各ヌクレオチドが右側と同一または優先である場合、これをパターン−1に分類する.例えば、AACCGTはパターン−1であるが、AACGTCはそうではない. 一般的に、DNA配列は、パターン−(j−1)またはパターン−(j−1)とパターン−1との結合に属する限り、パターン−j(j>1)に属する.例えば、AACCC、ACACC、ACACAはいずれもパターン−3であるが、GCAACおよびACACAはそうではない. 同様に、研究者たちは辞書順にDNA配列を並べ替えた.この定義によれば、パターン−3に属する最小DNA配列はAAAAAであり、最大はTTTTTである.ここで別の例として、未完了シーケンスACANNNNGを考える.では、最初の7つのこの未完成配列に適したDNA配列は、ACAAACAAG ACAAACG ACAAACAGG ACAAACACACACACACG ACAAACACACG ACACACACACACGG ACAAACCTG【タスク】を書くプログラムであり、辞書順のR番目の所定の長さMに適した未完成配列のパターン−Kを見つける.
問題解
この問題はおもしろいと思います.1つのDNA配列にいくつかの値を設定し、このテンプレート列のR番目のパターン−kを求めることを意味する.ここで私たちはまず問題の意味を理解する必要があります:様式-kは何を表していますか?パターン−2は1つの転換を有する列であり、パターン−3は最大2つの転換を有する列であり、パターン−kは最大k−1個の転換を有する列であることが分かる.ACGTをそれぞれ1,2,3,4にマッピングし、元の文字列を数字列strに変更すると、次のように定義できます.
隣接する2つの下付き文字について
i ,
i+1,若
str[i]>str[i+1]は、一次転換と呼ばれる.
 ここで要求される文字列には2つの制限がある:辞書順Rが大きく、転換はK-1を超えてはならない.辞書の順序については、多くの処理方法があります.典型的な例は次のとおりです.
FJOI最短パスツリーの問題
ZOJ2599 Graduated Lexicographical Ordering
 恩、FJOIとは関係ないに違いないが、ここではデジタルゲージの究極のテーマ:Graduated Lexicographical Orderingを考えている.ディクショナリシーケンスに基づいて数字列のサイズ比較を定義し、奇妙な制限があります.うん、その問題は今まで書く勇気がなかった......党を探して恐怖を示した......
本を本題に戻す.ここで私たちの要求は数位ゲージの思想と似ていて、ある属性が定値以下であることを要求して、もう一つの属性は列挙統計の性質を持っています:私たちは一人一人で現在の位置を列挙して何を記入することができて、もし事前にこの位置が記入した後に何種類を記入することができたら、私たちは簡単にここに記入した数が要求に合っているかどうかを計算することができます!
 記捜党は転送しかできないと表明した.この時、転送の構想が明らかにはっきりしているからだ.今、転送に何が必要か考えてみよう.現在処理されているビット数、現在準備されている数、すでに使用されている転換数の3つは、テーマで直接読むことができる情報です.もう十分ですか.答えは肯定的だ.
われわれは
f[i][now][ik]はi位に記入し、i位はnowを記入し、ik個の転換案数(文字列総数)を使用するので、移行方程式を書くことができます.
f[i][now][ik]={∑now−1lst=1f[i+1][lst][ik+1]+∑4lst=nowf[i+1][lst][ik]0if s[i]=now||s[i]=0else
境界条件は自分で押すことができて、私は書きません.
仕事はまだ終わっていない.ここでパターン-kが転換点であることに気づく
≦k−1のため、1つのメンテナンスが必要です.
fの接頭辞和
sum .
sum[i][now][ik]=∑p=1ikf[i][now][p]
 次に解の構造を考える:高位から低位まで辞書順に現在値をインクリメントし、算出された現在値がRより小さい場合、構造を継続する必要があることは明らかである.
R−=Sum[i][now][K]は、Rより大きい場所が見つかるまで.また,Kの制約は,制約に適応するために,小さいときから大きな辞書順を列挙するときにKのサイズを変更することに注意しなければならない.
注意すべき点:
 
パターン−kと転換点個数の関係を理解する.
逐位構造解の思想と原理を理解する.
 
ここは私が参考にしたブログです.
http://blog.sina.com.cn/s/blog_7e5d81d80100pzo6.html
http://www.docin.com/p-508754465.html
コード#コード#

#include<cstdio>
using namespace std;

typedef long long LL;
const int NUM=50005;

int m,K,str[NUM];
LL R,f[NUM][5][15],Sum[NUM][5][15];
char In[NUM];

inline int Code(char a)
{   int ret;
    //putchar(a);
    switch(a)
    {
      case 'A':ret=1;break;
      case 'C':ret=2;break;
      case 'G':ret=3;break;
      case 'T':ret=4;break;
      case 'N':ret=0;break;
    }
    return ret;
}
inline char Decode(int a)
{   char ret;
    switch(a)
    {
      case 1:ret='A';break;
      case 2:ret='C';break;
      case 3:ret='G';break;
      case 4:ret='T';break;
    }
    return ret;
}

void Read()
{   int i;
    scanf("%d%d%lld",&m,&K,&R);
    K--;//            
    scanf("%s",In);
    for(i=1;i<=m;i++)
     str[i]=Code(In[i-1]);//putchar('
');
    //for(i=1;i<=m;i++)
    // printf("%d",str[i]);putchar('
');
}
void Preload()
{   int i,now,ik,lst,Dw,Up;
    f[m+1][4][0]=1;//////////    
    for(i=m;i>=1;i--)
    { if(str[i])Dw=Up=str[i];
      else{ Dw=1;Up=4;}

      for(now=Dw;now<=Up;now++)
      { if(str[i]==now||str[i]==0)
        { for(lst=1;lst<now;lst++)
           for(ik=1;ik<=K;ik++)
            f[i][now][ik]+=f[i+1][lst][ik-1];
          for(lst=now;lst<=4;lst++)
           for(ik=0;ik<=K;ik++)
            f[i][now][ik]+=f[i+1][lst][ik];
        }
        else
         for(ik=0;ik<=K;ik++)
          f[i][now][ik]=0;
      }

      for(now=1;now<=4;now++)
      { Sum[i][now][0]=f[i][now][0];
        for(ik=1;ik<=K;ik++)
        Sum[i][now][ik]=f[i][now][ik]+Sum[i][now][ik-1];
      }
    }//printf("PreloadDONE
");
    /* for(i=m;i>=1;i--) { printf("i=%d
",i); for(now=1;now<=4;now++) { printf(" now=%d
 ",now); for(ik=0;ik<=K;ik++) printf(" %lld",Sum[i][now][ik]); putchar('
'); } } */
}
void Solve()
{   int i,now;
    str[0]=1;
    for(i=1;i<=m;i++)
    { K--;//        
      for(now=1;now<=4;now++)
      { if(now==str[i-1])K++;//    
        if(Sum[i][now][K]>=R)break;
        R-=Sum[i][now][K];
      }
      str[i]=now;
      putchar(Decode(str[i]));
    }
    putchar('
');
}
int main(){
    Read();
    Preload();
    Solve();
    return 0;
}