标签：
【BZOJ4606】[Apio2008]DNA Description
分析如DNA序列这样的生命科学数据是计算机的一个有趣应用。从生物学的角度上说,DNA 是一种由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶这四种核苷酸构成的链式布局。这四种核苷酸分袂用大写字母A、C、G、T暗示。这样,一条DNA单链可以被暗示为一个只含以上四种字符的字符串。我们将这样的字符串称作一个DNA序列 。有时生物学家可能无法确定一条DNA单链中的某些核苷酸。在这种情况下,字符N将被用来暗示一个不确定的核苷酸。换句话说,N可以用来暗示A、C、G、T中的任何一个字符。我们称包罗一个或者多个N的DNA序列为未完成序列;反之,就称作完成序列。
如果一个完成序列可以通过将一个未完成序列中的每个N任意替换成A、C、G、T得到的话,就称完成序列适合这个未完成序列。举例来说,ACCCT适合ACNNT,但是AGGAT不适合。研究者们经常凭据如下方法排序四种核苷酸:A优先于C,C优先于G,G优先于T。如果一个DNA序列中的每个核苷酸都与其右边的不异或者优先,就将其归类为范式-1。举例来说,AACCGT是范式-1,但是AACGTC不是。一般来说,一个DNA序列属于范式-j(j>1),只要它属于范式-(j-1)或者是一个范式-(j-1)和一个范式-1的连接。举例来说,AACCC、ACACC和ACACA都是范式-3,但GCACAC和ACACACA不是。同样,研究者们凭据字典序对 DNA 序列进行排序。凭据这个界说,最小的属于范式-3的DNA序列是AAAAA,最大的是TTTTT。这里是此外一个例子,考虑未完成序列 ACANNCNNG。那么前7个适合这个未完成序列的DNA序列是:
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
写一个措施,找到按字典序的第R个适合给定的长度为M的未完成序列的范式-K。
Input
输入第一行包罗三个由空格离隔的整数:M(1≤M≤50,000),K(1≤K≤10)和R(1≤R≤2×10^12)。
第二行包罗一个长度为M的字符串,暗示未完成序列。
保证适合该未完成序列的范式-K的总数不赶过4×10^18
因此该数可以用C和C++中的long long类型或者Pascal中的Int64类型暗示。
同时,R不会赶过适合给定未完成序列的范式-K的总数。
Output
在第一行中输出第R个适合输入中的未完成序列的范式-K。
Sample Input9 3 5
ACANNCNNG
ACAAACCCG
题意：我们界说一个串的范式=最少能将该串分成几多个持续的段，满足每段都是单调不降的（A<C<G<T）。现用A,C,G,T替换原串中的N，求在所有可能得到的串中，第R小的，范式<=K的串。
题解：觉得思路和数位DP仿佛。
先倒着DP，令f[i][j][k]暗示后i位，范式=k，，且第i位是j的串的个数。转移对照简单。最后我们再正着统计一遍。如果第i位=j时方案数<ans，就令ans-=方案数，并枚举j+1。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=50010; typedef long long ll; ll R; int n,m; int v[maxn]; ll f[maxn][4][10]; char str[maxn]; int main() { scanf("%d%d%lld%s",&n,&m,&R,str),m--; int i,j,k,l; for(i=1;i<=n;i++) { switch(str[i-1]) { case ‘A‘: v[i]=0; break; case ‘C‘: v[i]=1; break; case ‘G‘: v[i]=2; break; case ‘T‘: v[i]=3; break; case ‘N‘: v[i]=-1; break; } } f[n+1][3][0]=1; for(i=n;i>=1;i--) { for(j=0;j<4;j++) if(v[i]==-1||v[i]==j) for(k=0;k<=m;k++) { for(l=j;l<4;l++) f[i][j][k]+=f[i+1][l][k]; if(k) for(l=0;l<j;l++) f[i][j][k]+=f[i+1][l][k-1]; } } for(i=1;i<=n;i++) { for(j=0;j<4;j++) for(k=1;k<=m;k++) f[i][j][k]+=f[i][j][k-1]; for(j=0;j<4;j++) { ll tmp; if(j<v[i-1]) tmp=f[i][j][m-1]; else tmp=f[i][j][m]; if(R>tmp) R-=tmp; else break; } v[i]=j; if(v[i]<v[i-1]) m--; switch(v[i]) { case 0: str[i-1]=‘A‘; break; case 1: str[i-1]=‘C‘; break; case 2: str[i-1]=‘G‘; break; case 3: str[i-1]=‘T‘; break; case -1: str[i-1]=‘N‘; break; } } printf("%s",str); return 0; }
【BZOJ4606】[Apio2008]DNA DP