不等数列 (Dp插入e）

【题目描述】

将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。

【输入格式】

第一行2个整数n,k。

【输出格式】

一个整数表示答案。

【样例输入】

5 2

【样例输出】

66

【数据范围】

对于30%的数据：n <= 10

对于100%的数据：k < n <= 1000，

F[i,j]=f[i-1,j](j+1)+f[i-1][j-1](i-j) i表示从1到i的数 j表示小于号个数

插入最大数e后添了一个>

或者一个<的数量

var   b:array[1..10] of boolean;   f:array[0..10] of longint;   n,k,i:longint;procedure dfs(l,x,father:longint);var   i:longint;begin   if l=n then begin inc(f[x]); exit; end;   for i:=1 to n do   if not(b[i]) then   begin      b[i]:=true;      if father<i then dfs(l+1,x+1,i) else      dfs(l+1,x,i);      b[i]:=false;   end;end;begin   readln(n,k);   fillchar(b,sizeof(b),false);   fillchar(f,sizeof(f),0);   for i:=1 to n do   begin      b[i]:=true;      dfs(1,0,i);      b[i]:=false;   end;   for i:=0 to n-1 do write(f[i],' ');end.