# 3297. 铺瓷砖

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
//nowN 当前长度；one 长度为1的瓷砖块数；
int cnt_ans = 0; //方案数
int cnt_one = 0;

void DFS(int n, int nowN, int one, int pre, int now){
if(nowN > n || pre==now) return;
if(nowN==n){
cnt_ans++;
cnt_one += one;
}
//决策1：选1
DFS(n, nowN+1, one+1, now, 1);
//决策2：选2
DFS(n, nowN+2, one, now, 2);
//决策3：选3
DFS(n, nowN+3, one, now, 3);
}

int main(){

int T;
scanf("%d", &T);
while(T--){
int n; //地板总长度
scanf("%d", &n);

cnt_ans = 0;
cnt_one = 0;
DFS(n, 0, 0, -1, 0);
printf("%d\n%d\n", cnt_ans, cnt_one);
}

return 0;

}


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[31];
int dp1[31];
void dfs(int now,int a,int b,int c,int n,int last)
{
if (now>n) return;
if (now==n)
{
dp1[n]+=a;
dp[n]++;
}
if (last!=1) dfs(now+1,a+1,b,c,n,1);
if (last!=2) dfs(now+2,a,b+1,c,n,2);
if (last!=3) dfs(now+3,a,b,c+1,n,3);
}
int main()
{
for (int i=1;i<=30;i++) dfs(0,0,0,0,i,-1);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<dp[n]<<endl<<dp1[n]<<endl;
}
return 0;
}


DP

//状态：拼成前i段距离时，最后一个长度为j的最多拼法为dp[i][j]
#include <iostream>
#include <algorithm>
using namespace std;
int dp[31][4];
int dp1[31][4];
int n;
int main() {
int num;
cin >> num;
while (num--) {
cin >> n;
fill(dp[0], dp[0] + 31 * 4, 0);
fill(dp1[0], dp1[0] + 31 * 4, 0);
for (int i = 1; i <= 3; ++i) {
dp[i][i] = 1;
}
dp1[1][1] = 1;
for (int i = 3; i <= n; ++i) {
for (int j = 1; j <= 3; ++j) {
for (int k = 1; k <= 3; ++k) {
if (j == k) {
continue;
}
dp[i][j] = dp[i][j] + dp[i - j][k];
dp1[i][j] = dp1[i][j] + dp1[i - j][k];
if (j == 1) {
dp1[i][j] += dp[i - j][k];
}
}
}
}
int ans = 0;
ans = dp[n][1] + dp[n][2] + dp[n][3];
cout << ans << endl;
int ans1 = 0;
ans1 = dp1[n][1] + dp1[n][2] + dp1[n][3];
cout << ans1 << endl;
}
return 0;
}


### include

//前三个是不同长度下最大方法，后三个是不同长度下1的个数
int dp[30][6]={{1,0,0,1,0,0},{0,1,0,0,0,0},{1,1,1,1,1,0}};
int main()
{
int T;scanf(“%d”,&T);
for(int i =3;i<30;i++)
{
dp[i][0]=dp[i-1][1]+dp[i-1][2];
dp[i][1]=dp[i-2][0]+dp[i-2][2];
dp[i][2]=dp[i-3][0]+dp[i-3][1];
dp[i][3]=dp[i-1][4]+dp[i-1][5]+dp[i][0];
dp[i][4]=dp[i-2][3]+dp[i-2][5];
dp[i][5]=dp[i-3][3]+dp[i-3][4];
}
for(int num=0;num<T;num++)
{
int N;scanf(“%d”,&N);
int ways=dp[N-1][0]+dp[N-1][1]+dp[N-1][2];
int number=dp[N-1][3]+dp[N-1][4]+dp[N-1][5];
printf(“%d\n%d\n”,ways,number);
}
return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
int T;
cin >> T;
int dp[100];
int dp1[100][4];
dp[1] = 1;
dp[2] = 1;
dp[3] = 3;
dp1[1][1] = 1;
dp1[1][2] = 0;
dp1[1][3] = 0;

dp1[2][1] = 0;
dp1[2][2] = 1;
dp1[2][3] = 0;

dp1[3][1] = 1;
dp1[3][2] = 1;
dp1[3][3] = 1;

int dp3[100][4];

dp3[1][1] = 1;
dp3[1][2] = 0;
dp3[1][3] = 0;

dp3[2][1] = 0;
dp3[2][2] = 0;
dp3[2][3] = 0;

dp3[3][1] = 1;
dp3[3][2] = 1;
dp3[3][3] = 0;

while (T--) {
int N;
cin >> N;
for (int i = 4; i <= N; i++) {
dp[i] = dp[i - 3] - dp1[i - 3][3] + dp[i - 2] - dp1[i - 2][2] + dp[i - 1] - dp1[i - 1][1];
dp1[i][1] = dp[i - 1] - dp1[i - 1][1];
dp1[i][2] = dp[i - 2] - dp1[i - 2][2];
dp1[i][3] = dp[i - 3] - dp1[i - 3][3];

dp3[i][1] = dp3[i - 1][2] + dp3[i - 1][3] + dp1[i][1];
dp3[i][2] = dp3[i - 2][1] + dp3[i - 2][3];
dp3[i][3] = dp3[i - 3][1] + dp3[i - 3][2];;
}
cout << dp[N] << endl;
cout << dp3[N][1] + dp3[N][2] + dp3[N][3] << endl;
}

return 0;
}


### include

using namespace std;
int number;
int t;
int N[31];
void cl()
{
for(int i=1;i<=30;i++)
{
N[i]=0;
}
}
void f(int k,int n,int depth)
{
int d=depth+1;
if(n<0)
{
return;
}
if(n==0)
{
number++;
for(int i=1;i<=depth;i++)
{
if(N[i]==1)
t++;
}
return;
}
if(k==0)
{
N[d]=1;
f(1,n-1,d);
N[d]=2;
f(2,n-2,d);
N[d]=3;
f(3,n-3,d);
}
if(k==1)
{
N[d]=2;
f(2,n-2,d);
N[d]=3;
f(3,n-3,d);
}
if(k==2)
{
N[d]=1;
f(1,n-1,d);
N[d]=3;
f(3,n-3,d);
}
if(k==3)
{
N[d]=1;
f(1,n-1,d);
N[d]=2;
f(2,n-2,d);
}
}
int main()
{
int T;
int n;
cin>>T;
for(int i=0;i>n;
number=0;
t=0;
cl();
f(0,n,0);
cout<<number<<endl;
cout<<t<<endl;
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
int t, n, dp[31][4][2];
int yu[][2] = {{0,0},{2,3},{1,3},{1,2}};
int main(){
cin >> t;
while(t--){
cin >> n;
memset(dp,0,sizeof dp);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= 3; ++j){
if(i - j == 0){
dp[i][j][0] = 1;
dp[i][j][1] = (j==1) ? 1 : 0;
}
else if(i > j){
dp[i][j][0] = dp[i-j][yu[j][0]][0] + dp[i-j][yu[j][1]][0];
if(j == 1){
if(dp[i-1][2][0])
dp[i][1][1] += dp[i-1][2][0] + dp[i-1][2][1];
if(dp[i-1][3][0])
dp[i][1][1] += dp[i-1][3][0] + dp[i-1][3][1];
}
else
dp[i][j][1] += dp[i-j][yu[j][0]][1] + dp[i-j][yu[j][1]][1];
}

}
//printf("%d %d %d \n", dp[i][1][1],dp[i][2][1],dp[i][3][1]);
}
cout << dp[n][1][0] + dp[n][2][0] + dp[n][3][0] << endl;
cout << dp[n][1][1] + dp[n][2][1] + dp[n][3][1] << endl;
}
}


DFS

#include <iostream>
using namespace std;
int n;
int ans;
int res_1;
int res_2;
void DFS(int sum, int res, int res_1) {
if (sum > n) {
return;
}
if (sum == n) {
ans++;
res_2 += res_1;
return;

}
if (res == 0) {
DFS(sum + 1, 1, res_1 + 1);
DFS(sum + 2, 2, res_1);
DFS(sum + 3, 3, res_1);

}
else if (res == 1) {
DFS(sum + 2, 2, res_1);
DFS(sum + 3, 3, res_1);
}
else if (res == 2) {
DFS(sum + 1, 1, res_1 + 1);
DFS(sum + 3, 3, res_1);
}
else if (res == 3) {
DFS(sum + 1, 1, res_1 + 1);
DFS(sum + 2, 2, res_1);
}
}

int main() {
int num;
cin >> num;
while (num--) {
cin >> n;
ans = 0;
res_1 = 0;
res_2 = 0;
DFS(0, 0, 0);
cout << ans << endl;
cout << res_2 << endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR0(a,b) for(int i = a; i < b; ++i)
#define FORE(a,b) for(int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int,int> pii;
const int f[] = {1,2,3};
int ans = 0, yi = 0, n;
void dfs(int sum, int pre, int fir) {
if(sum > n) return;
if(sum == n) {
// cout << yi << endl;
ans++;
yi+=fir;
return;
}
for(int i = 0; i < 3; ++i)  {
if(f[i] == pre) continue;
dfs(sum+f[i],f[i],fir+(f[i]==1));
}
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
ans = 0, yi = 0;
scanf("%d", &n);
dfs(0,0,0);
cout << ans << endl << yi << endl;
}
return 0;
}


### include

using namespace std;

### define FORE(a,b) for(int i = a; i <= b; ++i)

typedef long long ll;
typedef pair pii;
const int f[] = {1,2,3};
int ans = 0, yi = 0, n;
void dfs(int sum, int pre, int fir) {
if(sum > n) return;
if(sum == n) {
// cout << yi << endl;
ans++;
yi+=fir;
return;
}
for(int i = 0; i < 3; ++i) {
if(f[i] == pre) continue;
dfs(sum+f[i],f[i],fir+(f[i]==1));
}
}
int main() {
int T;
scanf(“%d”, &T);
while(T–) {
ans = 0, yi = 0;
scanf(“%d”, &n);
dfs(0,0,0);
cout << ans << endl << yi << endl;
}
return 0;
}