hihocoder-1732-1-偏差排列
#1732 : 1-偏差排列
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如果一个1~N的排列P=[P1, P2, ... PN]中的任意元素Pi都满足|Pi-i| ≤ 1，我们就称P是1-偏差排列。
给定一个N，请你计算一共有少个不同的排列是1-偏差排列。
例如对于N=3，有3个1-偏差排列：[1, 2, 3], [1, 3, 2], [2, 1, 3]。
输入
一个整数N。
对于50%的数据，1 ≤ N ≤ 15
对于100%的数据，1 ≤ N ≤ 50
输出
一个整数表示答案
- 样例输入
-
3
- 样例输出
-
3
找规律，一个数字i，只能在i-1, i, i+1这三个位置存在。
dp[n][0] 表示第n个位置为n的合法数组种类数，dp[n][1]表示第n个位置为n-1，n在位置n-1的合法数组的种类数
对于原本n个元素的数组，插入一个n+1，有两种插入方法，
放在n+1位置， 则dp[n+1][0] = dp[n][0] + dp[n][1];
放在n-1位置， 则 dp[n+1][1] = dp[n][0];
该种类数组成的序列是斐波纳挈序列。f[n] = f[n-1] + f[n-2]； 为其简化版本。
#include <cstdio>
#include <cstdlib>
const int MAXN = 100 + 10;
int n;
long long ans, dp[MAXN][2];
void init(){
dp[1][0] = 1;
dp[1][1] = 0;
for(int i=2; i<MAXN; ++i){
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
}
int main(){
init();
while(scanf("%d", &n) != EOF){
ans = dp[n][0] + dp[n][1];
printf("%lld
", ans );
}
return 0;
}