codevs4817 *的dp题d

时间:2024-01-20 10:06:03

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没有放在第一个位置放在哪里的方案数。