4817 江哥的dp题d
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
【题目描述】 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
【题目分析】
从小到大一个一个往数列里加数字，第一次加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没有放在第一个位置放在哪里的方案数。