首页 > ACM题库 > HDU-杭电 > HDU 4689-Derangement-动态规划-[解题报告]HOJ
2015
09-17

HDU 4689-Derangement-动态规划-[解题报告]HOJ

Derangement

问题描述 :

A derangement is a permutation such that none of the elements appear in their original position. For example, [5, 4, 1, 2, 3] is a derangement of [1, 2, 3, 4, 5]. Subtracting the original permutation from the derangement, we get the derangement difference [4, 2, -2, -2, -2], where none of its elements is zero. Taking the signs of these differences, we get the derangement sign [+, +, -, -, -]. Now given a derangement sign, how many derangements are there satisfying the given derangement sign?

输入:

There are multiple test cases. Process to the End of File.
Each test case is a line of derangements sign whose length is between 1 and 20, inclusively.

输出:

There are multiple test cases. Process to the End of File.
Each test case is a line of derangements sign whose length is between 1 and 20, inclusively.

样例输入:

+-
++---

样例输出:

1
13

题意:

艰涩难懂的题意!,n个1,2,3…n的数,它的错排,错排后的序列与原来的序列相减,满足给定的符号。(+,-)。

我dp好惨啊,不会搞啊!

dp[i][j]表示前i个还有j个符号没确定。如果是第i个是加号,则从前面选,否则从后面选。

#include<cstdio>
#include<cstring>
typedef long long LL;
using namespace std;
int main()
{
	LL i,j,n;
	LL dp[22][22];
	char str[22];
	while(scanf("%s",str)!=EOF){
		n=strlen(str);
		if(str[0]=='-'){  
			puts("0");
			continue;
		}
		memset(dp,0,sizeof(dp));
		dp[1][1]=1;
		for(i=2;i<=n;i++){
			if(str[i-1]=='+'){
				for(j=1;j<=i;j++){
					dp[i][j]+=dp[i-1][j-1];
					dp[i][j]+=dp[i-1][j]*j;
				}
			}
			else{
				for(j=1;j<=i;j++){
					dp[i][j-1]+=dp[i-1][j]*j*j;
					dp[i][j]+=dp[i-1][j]*j;
				}
			}
		}
		printf("%I64d\n",dp[n][0]);
	}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/chj_zmr/article/details/10172365