【NOIP2016DP专题】DNA序列

发布于 2016-11-15  504 次阅读


Description

来自JSSI(Jinkela State Scientific Institute)的科学家们尝试制造一个长度为N并且只包含A的DNA序列,不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改,来得到一个全部是A的序列。 篡改的方式有两种:

1 更改某一位上部件的状态(A变成B,B变成A)

2 更改某个前缀内所有部件的状态 两种操作的代价都为1。

你的任务自然是求最小代价。

Input Format

第一行为N,序列长度。

第二行是一个长度为N且只包含A和B的字符串,表示初始序列。

Output Format

最小代价。

Sample Input

12
AAABBBAAABBB

Sample Output

4

Hint

数据范围

对于10%的数据,N<=10

对于70%的数据,N<=100000

对于100%的数据,N<=1000000


题目分析:f[i][0]表示前i个全部为A的方案数,f[i][1]表示为B的方案数。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;
int f[1000005][2],n;
char s;
int main(){
  	scanf("%d\n",&n);
  	For (i,n){
  	  	scanf("%c",&s);
  	  	if (s=='A') f[i][0]=f[i-1][0],f[i][1]=f[i-1][1]+1;
  	  	else f[i][0]=f[i-1][0]+1,f[i][1]=f[i-1][1];
  	  	if (f[i][0]<f[i][1]) f[i][1]=min(f[i][1],f[i][0]+1);
  	  	else f[i][0]=min(f[i][0],f[i][1]+1);
	}
	printf("%d",f[n][0]);
} 

「知我罪我,其惟春秋」