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;
}