题目
不容易系列之(3)―― LELE的RPG难题
思路
简单的DP题。
代码
#include<bits/stdc++.h>
using namespace std;
//默认以0开头,以1和2结尾。f[i][1]表示长度为i的以1结尾的涂抹方案
//状态转移方程:若以1结尾,则前面一个格子只能是0或者2
//f[i][1] = f[i - 1][0] + f[i - 1][2];
long long a[52][3];
int main() {
//我们默认0为开头,长度为1时开头即结尾。
// a[1][0] = 1, a[1][1] = 0, a[1][2] = 0;
a[2][0] = 0, a[2][1] = 1, a[2][2] = 1;
int n;
for(int i = 3; i <= 50; i ++) {
a[i][0] = a[i - 1][1] + a[i - 1][2];
a[i][1] = a[i - 1][0] + a[i - 1][2];
a[i][2] = a[i - 1][0] + a[i - 1][1];
}
while(cin >> n) {
if(n == 1)
cout << 3 << endl;
else
cout << 3 * (a[n][1] + a[n][2]) << endl;
}
return 0;
}