首页 > 代码库 > 不等式数列 DP
不等式数列 DP
度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>‘ 和 ‘<‘ )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即(‘<‘‘)和n-k-1个大于符号(即‘>‘),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。
输入描述:
输入包括一行,包含两个整数n和k(k < n ≤ 1000)
输出描述:
输出满足条件的排列数,答案对2017取模。
输入例子:
5 2
输出例子:
66
题解：
我们考虑用dp[i][j]表示1-i这i个数字，里面的i-1个空隙里有j个小于号，i-j-1个大于号的方案数
两边很好考虑，如果插入中间某个位置的话，必然会在两边有一个小于号和一个大于号
那么枚举这个位置原来是什么号就知道哪个号多了一个辣！
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 1e3+10, M = 1e3+20, mod = 2017,inf = 2e9;int n,k;LL dp[N][N];int main(){ scanf("%d%d",&n,&k); dp[1][0] = 1; for(int i = 1; i <= n; ++i) { for(int j = 0; j < i; ++j) { dp[i+1][j] += dp[i][j]*(j+1); dp[i+1][j] %= mod; dp[i+1][j+1] += dp[i][j]*(i-1-j+1); dp[i+1][j+1] %= mod; } } printf("%lld\n",dp[n][k]); return 0;}
不等式数列 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。