#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 == 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; } } |
Double click to view unformatted code.