
题目描述 Description
已知1~N的排列P的LIS(最长上升子序列)不超过2,求可能的P的个数。答案取模10^9+7。
输入描述 Input Description
一行一个整数N。
输出描述 Output Description
输出一行一个整数,描述可能的排列P的个数mod1000000007的结果。
样例输入 Sample Input
1
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
测试点编号 数据范围
1,2 N≤10
3,4 N≤20
5,6,7,8,9,10 N≤1000
AC代码:
/*解析:
从小到大一个一个往数列里加数字,第一次加1,只有一种加法,第二次加2,可以加在1前或后,2种方法.....
最长上升子序列要么是1要么是2,是1的话只有一种情况,下降序列
f[i][j]表示已经加了前i个数字,最后一个数字(第i个数)的位置是j,满足题目要求的方案数,
如果i不是加在第一个位置是,i+1必须在i的前面,
否则你会形成一个3的上升子序列。
所以当j不等于1时,你只能把i+1加到i前面。
如果j==1,可以加到第1,2,3个位置,第四个位置就无法确定了,
所以我们改变策略。
f[i][j]表示前i个数字已经放好且j表示i没有放在第一个位置放在哪里的方案数。
*/
#include<cstdio>
using namespace std;
const int N=1e3+;
const int mod=;
int n,f[N][N]={};
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
f[i][j]=(f[i][j-]+f[i-][j])%mod;
}
}
printf("%d",f[n][n]);
return ;
}