Problem 2 不等数列(num.cpp/c/pas)
【题目描述】
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。
【输入格式】
第一行2个整数n,k。
【输出格式】
一个整数表示答案。
【样例输入】
5 2
【样例输出】
66
【数据范围】
对于30%的数据：n <= 10
对于100%的数据：k<n<=1000，
乍一看，好像是动态规划，仔细看，还真是动态规划（以上为本人卖萌）
说正经题解：
因为此题只需要得出数字之间的大小关系，而并不需要得出具体的数字之间的差值，所以可以看为从小到大向一个数列中插入数字，这样就是只需要记录第几个数字被插入就可以了，同时记录插入到这时的“<”的数量。
使用一个二维数组记录，分别记录插入的数字与已有的“<”个数，于是转移方程就出来了：
f[i][j]=(f[i-1][j-1]*(i-j))+(f[i-1][j]*(j+1))
这由两种情况组成：
插入“<”连接的两个数字之中，由于是从大到小插入，所以小于号数量并没有改变
如果插入">"连接的两个数字中，小于号会增加一个。
最后f[n][k]就是答案
#include<cstdio> int n,k,i,j; int f[1003][1003]; void read(int &y) { y=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int main() { read(n);read(k); for(i=1;i<=n;i++) f[i][0]=1; f[2][1]=1; for(i=3;i<=n;i++) { for(j=1;j<i;j++) f[i][j]=(f[i-1][j-1]*(i-j))%2015+(f[i-1][j]*(j+1))%2015; } printf("%d",f[n][k]%2015); return 0; }