[HOJ] 178 - 龍使之HSNU-HOT

#include<stdio.h>
#include<algorithm>
using std::min;
int dp[1000005][2];
char s[1000005];
int main(){
    int t,n,i,tmp;
    scanf("%d",&t);
    while(t--){
        dp[0][0]=dp[0][1]=0;
        scanf("%d%s",&n,&s[1]);
        for(i=1;i<=n;i++){
            if(s[i]=='A'){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
            }
            else{
                dp[i][1]=dp[i-1][1];
                dp[i][0]=min(dp[i-1][1],dp[i-1][0])+1;
            }
        }
        printf("%d\n",dp[n][0]);
    }

}