「NOIP模拟赛」DNA序列

2014年4月5日3,2700

题目描述

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

1 更改某一位上部件的状态（A变成B，B变成A）

2 更改某个前缀内所有部件的状态

两种操作的代价都为1。

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

输入

第一行为N，序列长度。

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

输出

最小代价。

样例输入

样例输出

数据范围

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

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

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

题解

直接dp或者倒过来贪心都行

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
int n,f[1000001][2];//0A,1B
char ch[1000001];
int main()
{
	//freopen("dna.in","r",stdin);
	//freopen("dna.out","w",stdout);
	scanf("%d%s",&n,ch);
	for(int i=1;i<=n;i++)
	{
		if(ch[i-1]=='A')
		{
			f[i][0]=f[i-1][0];
			f[i][1]=min(f[i-1][1],f[i-1][0])+1;
		}
		else 
		{
			f[i][1]=f[i-1][1];
			f[i][0]=min(f[i-1][0],f[i-1][1])+1;
		}
	}
	printf("%d",f[n][0]);
	return 0;
}

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#define ll long long

using namespace std;

int n,f[1000001][2];//0A,1B

char ch[1000001];

int main()

{

//freopen("dna.in","r",stdin);

//freopen("dna.out","w",stdout);

scanf("%d%s",&n,ch);

for(int i=1;i<=n;i++)

{

if(ch[i-1]=='A')

{

f[i][0]=f[i-1][0];

f[i][1]=min(f[i-1][1],f[i-1][0])+1;

}

else

{

f[i][1]=f[i-1][1];

f[i][0]=min(f[i-1][0],f[i-1][1])+1;

}

printf("%d",f[n][0]);

return 0;

}

« 「BZOJ1616」[Usaco2008 Mar] Cow Travelling游荡的奶牛「BZOJ1669」[Usaco2006 Oct] Hungry Cows饥饿的奶牛 »

hzwer.com _ Home | http://hzwer.com

「NOIP模拟赛」DNA序列

分类目录

热门文章

Myfriends

近期评论