字符序列（题解）

字符序列(characts)

问题描述：

从三个元素的集合[A,B,C]中选取元素生成一个N 个字符组成的序列，使得没有两个相邻的子序列（子序列长度＝2）相同，例：N＝5 时ABCBA 是合格的，而序列ABCBC 与ABABC 是不合格的，因为其中子序列BC，AB 是相同的。

输入N（1<=N<=12）,求出满足条件的N 个字符的所有序列和其总数。

输入样例1：

4

输出样例1：

72

输入样例2：

2

输出样例2：

9

这道题可以用模拟的思想：给定一个字符串，对于当前这位和前面的第二位；这一位的前面的第一位和这一位前面的第三位，来进行比较。如果他们相等的话，就表明肯定是不符合的；如果他们不相等的话，就可以进行下一位的判断。

当然，这些是基于字符的操作。所以，还有一种更简便的算法：把A、B、C看作数字1、2、3，每次进行+1操作。如果+1后的数超过3，就可以从1开始继续加，最后用DFS串一下就可以解决了。

代码：

#include<cstdio>
#include<cmath>
#define end return
int n,sum=0;
int ans[15];
bool pd()
{
    int cnt=0;
    for(int i=3; i<=n; i++)
    {
        if(ans[i]==ans[i-2])
            cnt++;
        else
        {
            cnt=0;
        }
        if(cnt==2)
            end 0;
    }
    end 1;
}
void dfs(int x)
{
    if(x == n + 1)
    {
        if(pd())
            sum++;
        end;
    }
    for(int i=1; i<=3; i++)
    {
        ans[x]=i;
        dfs(x+1);
    }
}
int main()
{
    //freopen("characts.in","r",stdin),freopen("characts.out","w",stdout);
    scanf("%d",&n);
    dfs(1);
    printf("%d",sum);
    end 0;
}