这一题纯找规律

首先，我们观察题面，注意到1<=n<=30， 暴力3^30必然$TLE$，凭借做题直觉可判断这题很可能有某种规律($dp$)

所以我们可以先写一下 $dfs$ 找规律：

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
int ans;
int a[35];
bool check(){
	for(int i=1;i<=n-2;i++){
		bool c[4]={0};
		for(int j=i;j<=i+2;j++){
			c[a[j]]=1;
		}
		bool ok=0;
		for(int i=1;i<=3;i++){
			if(!c[i]){
				ok=1;
				break;
			}
		}
		if(!ok) return 0;//是 fstring 字符串 
	}
	return 1;//反之 
}
void dfs(int t){
	if(t==n+1){
		if(check()) ans++;
		return;
	}
	a[t]=1;
	dfs(t+1);
	a[t]=2;
	dfs(t+1);
	a[t]=3;
	dfs(t+1);
	return;
}
signed main(){
	m=read();
	for(n=1;n<=m;n++){
		ans=0;
		dfs(1);
		cout<<n<<' '<<ans<<'\n';
	}
	return 0;
}//注意是有多少个不是fstring字符串

输入15得： 1 3 2 9 3 21 4 51 5 123 6 297 7 717 8 1731 9 4179 10 10089 11 24357 12 58803 13 141963 14 342729 15 827421

通过观察发现（怎么每次都是观察）， $ans[i]=ans[i-1]*2+ans[i-2]$， 于是便有了下面的$AC代码$：

#include<bits/stdc++.h>
#define int long long//十年OI一场空，不开long long见祖宗
//一定一定一定要开 long long!以后比赛能开long long尽量开long long
//(我很多次因没开long long而未能 AC ) 
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
int last2,last,ans;
signed main(){
	n=read();
	if(n==1){cout<<3;return 0;}
	if(n==2){cout<<9;return 0;}//注意特判 
	last2=3;//初始化，n=1时的答案为 3
	last=9;//n=2时的答案为 9
	for(int i=3;i<=n;i++){
		ans=(last<<1)+last2;//=ans=last*2+last2
		last2=last;last=ans;
	}//f[i]=f[i-1]*2+f[i-2]
	cout<<ans;
	return 0;
}