HDU4689 Derangement

2013多校, DP, HDU

　　2013 Multi-University Training Contest 9

　　题意：定义初始排列为1、2、…、n，定义一个n排列A[]， 若i>A[i]表示为’+’，i

　　新队伍组队第一场啊，有DP大佬队友的感觉真是好。

　　f[i][j]表示放置用前i个数字放置前i个位置，填满了所有’-‘，剩下j个’+’没填（也相当于有j个数字要放置到第i+1~n位）的总方案数。

　　初始条件f[0][0]=1，转移如下：

  • 当a[i]为’+’
    • 当前数字i在前面挑一个’+’放置，此时当前’+’未填，j不变：f[i][j]+=f[i-1][j]*j
    • 当前数字i不放置，此时当前’+’未填，j增加：f[i][j]+=f[i-1][j-1]
  • 当a[i]为’-‘
    • 在前j个未放置的数字中挑选一个放置到当前位置，当前数字i不放置，此时j不变：f[i][j]+=f[i-1][j]
    • 在前j+1个未放置的数字中挑选一个放置到当前位置，当前数字i在前面挑一个’+’放置，此时j减少：f[i][j]+=f[i-1][j+1]*(j+1)*(j+1)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=20+5;
typedef long long lint;
lint f[maxn][maxn];
char s[maxn];
int main()
{
	while(scanf("%s", s+1)!=EOF)
	{
		int n=strlen(s+1);
		memset(f, 0, sizeof f);
		f[0][0]=1;
		for(int i=1; i<=n; i++)
			for(int j=0; j<=i; j++)
			{
				if(s[i]=='+')
				{
					f[i][j]+=f[i-1][j]*j;
					if(j)	f[i][j]+=f[i-1][j-1];
				}
				else	f[i][j]+=(f[i-1][j]*j+f[i-1][j+1]*(j+1)*(j+1));
			}
		printf("%lld\n", f[n][0]);
	}
	return 0;
}