View Code of Problem 3692

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

//void dfs(int& res, vector<int>& map, int n) {
//
//	if (map.size() == n) {
//
//		res++;
//		return;
//	}
//
//	for (int i = 1; i <= 3; i++) {
//
//		if (map.size() == 0)
//			map.push_back(i);
//		else {
//			if (map.size() == n - 1) {
//
//				if (i == map[map.size() - 1] || i == map[0])
//					continue;
//			}
//			else {
//
//				if (i == map[map.size() - 1])
//					continue;
//			}
//			
//			map.push_back(i);
//		}
//
//		dfs(res, map, n);
//
//		map.pop_back();
//	}
//}
//
//int main()
//{
//	int n;
//	while (cin >> n) {
//
//		vector<int> map;
//
//		int res = 0;
//		dfs(res, map, n);
//
//		cout << res << endl;
//	}
//}

//以上为dfs打表法，再找规律，否则会超时
int main()
{
	int n;
	while (cin >> n) {

		if (n == 0) {

			cout << 0 << endl;
			continue;
		}

		if (n == 1) {

			cout << 3 << endl;
			continue;
		}
		if(n == 2 || n == 3){
		
			cout << 6 << endl;
			continue;
		}

		vector<long long> dp(n + 1);
		dp[1] = 3;
		dp[2] = 6;
		dp[3] = 6;

		for (int i = 4; i <= n; i++)
			dp[i] = dp[i - 2] * 2 + dp[i - 1];

		cout << dp[n] << endl;
	}
}