大意略。
思路:很明显,奇数无解,考虑偶数。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; int f[35], g[35]; int n; void init() { f[0] = 1, f[1] = 0; g[0] = 0, g[1] = 1; for(int i = 2; i <= 31; i++) { f[i] = f[i-2] + 2*g[i-1]; g[i] = f[i-1] + g[i-2]; } } int main() { init(); while(~scanf("%d", &n) && n != -1) { printf("%d\n", f[n]); } return 0; }