DNA-AND-DNA

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 91   Accepted Submission(s) : 45

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

生物学家们发现了一个奇怪的DNA分子，可以将它们看作一个由集合{A，B} 中的元素组成的N个字符的序列。由于一系列的突变使得DNA链只包含A。生物学家发现这很奇怪，所以他们开始研究更详细的基因突变。他们发现了两种类型的基因突变。一种类型是改变单个字符的序列（A→B或B→A）。第二类改变了整个序列的前缀，从1到K（1和N之间）。计算数量尽可能少的突变，可以是起始分子转化到它的最终状态（只包含A字符）。突变可以在任何顺序发生。

Input

输入有多组数据。输入的第一行包含一个正整数N（1≤N≤1000 000），表示分子的长度。输入第二行包含N个字符的字符串，这个字符串由A或B组成，表示DNA分子的起始状态。

Output

输出的一行表示必须的最低数量的突变。

Sample Input

4ABBA5BBABB12AAABBBAAABBB

Sample Output

224 不得不让我感叹DP的神奇。。两句话搞定。。O（n)的时间复杂度

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int N;int dp[1000100][2];/*dp[i][0]表示前i个字符全是Adp[i][1]表示前i个字符全是B*/ char str[1000100];int main( ){  while( scanf("%d", &N) != EOF )  {      scanf("%s",str + 1);     memset(dp,0,sizeof(dp));     for( int i = 1; i <= N; i++)     {       dp[i][0] = min(dp[i-1][0] + (str[i] == 'B'), dp[i-1][1] + 1 + (str[i] == 'A'));       dp[i][1] = min(dp[i-1][0] + 1 + (str[i] == 'B'), dp[i-1][1] + (str[i] == 'A'));      }     printf("%d\n", min(dp[N][0], dp[N][1]+1));      }  return 0;  }