[题] 不容易系列之(3)―― LELE的RPG难题 #DP

题目

不容易系列之(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;
}