HDOJ 3664 Permutation Counting / UVALive 5092 DP

这个题呢，一开始是用DP想的，但是没有按照DP的思路走，因为题目意思描述得很简单，显然是可以打表找规律的

先附上打表的程序

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

int dp[10][10],n;
int num[10];
bool vis[10];

void calc(){
	//for(int i=1;i<=n;i++)
	//	printf("%d%c",num[i],i==n?'\n':' ');
	int res=0;
	for(int i=1;i<=n;i++)
		if (num[i]>i) res++;
	dp[n][res]++;
}

void dfs(int step){
	if (step>n) calc();
	for(int x=1;x<=n;x++)
		if (!vis[x]){
			num[step]=x;
			vis[x]=true;
			dfs(step+1);
			vis[x]=false;
		}
}

int main(){
	n=7;
	memset(dp,0,sizeof(dp));
	memset(vis,false,sizeof(vis));
	dfs(1);
	for(int i=0;i<=n;i++)
		printf("%d%c",dp[n][i],i==n?'\n':' ');
	return 0;
}

代码就是用dfs生成了所有的排列，然后根据题意统计，dp【i】【j】：有i个数字，j个根据题意的匹配

我们可以修改n，n=3，4，5，6，7，8，……这些小数据打出来一个表，然后可以来找规律（这是一种可行的方法）

但是dp的方法呢，来递推公式：

dp【i】【j】会怎么来：

第一部分：dp【i-1】【j】，最大的第i个数放在最后面

第二部分：dp【i-1】【j】*j，最大的第i个数与前i-1个数字中的j个比原来位置上的数大的数互换位置，匹配值不变

第三部分：dp【i-1】【j-1】*（i-1-（j-1）），因为要增加一个匹配，就不能在原来已经有匹配的位置上选择

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define ll long long
const int maxn=1010;
ll dp[maxn][maxn];
const int mod=1e9+7;

int main(){
	//freopen("input.txt","r",stdin);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=1000;i++){
		dp[i][0]=1;
		for(int j=1;j<=i;j++)
			dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j))%mod;
	}
		int n,k;
		while(scanf("%d%d",&n,&k)!=EOF)
			printf("%lld\n",dp[n][k]);
	return 0;
}