洛谷P7767 DNA 题解

Problem

Solution

考虑 DP。

设 \(dp_{i,0}\) 表示前 \(i\) 个字符全为 A 的最小操作次数，\(dp_{i,1}\) 表示前 \(i\) 个数全为 B 的最小操作次数。

考虑转移。

若当前位为 A 则 \(dp_{i,0}=\min(dp_{i-1,0},dp_{i-1,1}+1)\)，\(dp_{i,1}=\min(dp_{i-1,0}+1,dp_{i-1,1}+1)\)；

若当前位为 B 时同理。

最后输出 \(\min(dp_{n,0},dp_{n,1}+1)\) 即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
namespace IO
{
	inline int read()
	{
		register int x=0,f=0;register char ch=getchar();
		while(ch<'0' || ch>'9')f|=ch=='-',ch=getchar();
		while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
		return f?-x:x;
	}
	int min(int x,int y){return x<y?x:y;}
}
using namespace IO;

const int N=1e6+4;
int n,dp[N][2];
string S;
int main()
{
	cin>>n>>S;
	S=" "+S;
	// dp[i][0] i,A
	// dp[i][1] i,B
	memset(dp,0x3ffffff,sizeof(dp));
	if(S[1]=='A')dp[1][0]=0,dp[1][1]=1;
		else dp[1][0]=1,dp[1][1]=0;
	For(i,2,n)
		if(S[i]=='A')dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1),dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);
			else dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1),dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]);
	cout<<min(dp[n][0],dp[n][1]+1);

	return 0;
}