首页 > 代码库 > hdu3664（递推dp）
hdu3664（递推dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3664
分析：dp[i][j]表示i个数的排列中E值为j的个数。假设现在已有一个E值为j的i的排列，对于新加入的一个数i+1,将其加入排列的方法有三：
1)把它放最后，加入后E值不变
2)把它和一个满足A[k]>k的数交换，A[k]到最后，A[k]必定小于i+1，交换后E值不变，符合这样的k共有j个
3)把它和一个不满足A[k]>k的数交换，A[k]到最后，A[k]必定小于i+1，交换后E值+1，符合这样的k共有i-j个
根据这三种方法得到转移方程dp[i][j] = dp[i - 1][j] + dp[i - 1][j] * j + dp[i - 1][j - 1] * (i - j);
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;LL f[1010][1010];void init(){ for (int i=1;i<=1000;i++) { f[i][0]=1; for (int j=1;j<i;j++) f[i][j]=((j+1)*f[i-1][j]+(i-j)*f[i-1][j-1])%mod; }}int main(){ int n,k; init(); while (scanf("%d%d",&n,&k)>0) printf("%I64d\n",f[n][k]); return 0;}
hdu3664（递推dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。