首页 > 代码库 > HDOJ 4689 Derangement DP

HDOJ 4689 Derangement DP

2024-07-31 12:22:41   221人阅读


DP详解见:

http://blog.csdn.net/liguan1/article/details/10468139

Derangement

Time Limit: 7000/7000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 846    Accepted Submission(s): 256


Problem Description
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?
 

Input
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.
 

Output
For each test case, output the number of derangements.
 

Sample Input
+-
++---
 

Sample Output
1
13
 

Author
Zejun Wu (watashi)
 

Source
2013 Multi-University Training Contest 9
 


#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

LL dp[50][50];
char str[50];

int main()
{
    while(cin>>str)
    {
        if(str[0]=='-')
        {
            puts("0"); continue;
        }
        memset(dp,0,sizeof(dp));
        int n=strlen(str);
        dp[1][1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(str[i-1]=='+')
                {
                    if(j) dp[i][j]+=dp[i-1][j-1];
                    dp[i][j]+=dp[i-1][j]*j;
                }
                else if(str[i-1]=='-')
                {
                    dp[i][j]+=dp[i-1][j]*j;
                    dp[i][j]+=dp[i-1][j+1]*(j+1)*(j+1);
                }
            }
        }
        cout<<dp[n][0]<<endl;
    }
    return 0;
}



HDOJ 4689 Derangement DP


联系
我们