2020HDU多校赛第十场 Permutation Counting

题意:用一个长度为n的排列，生成一个长度为n-1的up-down序列。若后一个比前一个大，则为0。反之，则为1。给定一个长度为n-1的updown序列，问符合序列的合法排列数量.

例：1,2,3,6,4,5 is 0,0,0,1,0.

分析：设状态 前1-i数字放置并且最后第i个位置放j的合法方案数，如果输入序列的第i位是0, 就需要往 转移, 否则需要往 转移. 利用前缀和优化一下 DP 即可做到 .

#include<bits/stdc++.h>

using namespace std;

const int mod=1e9+7;
int dp[5005][5005];
int sum[5005][5005];
int b[5005];

int main()
{
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        int n;
        scanf("%d",&n);
        for( int i=2;i<=n;i++ ) scanf("%d",&b[i]);
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;

        for( int i=2;i<=n;i++ )
        {
            for( int j=1;j<i;j++ )
            {
                if( b[i]==0 ) dp[i][j+1]=(dp[i][j+1]+dp[i-1][j])%mod;
                else dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
            }
            if( b[i]==0 )
            {
                for( int j=1;j<=i;j++ ) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
            }
            else
            {
                for( int j=i;j>=1;j-- ) dp[i][j]=(dp[i][j]+dp[i][j+1])%mod;
            }    
        } 
        int ans=0;
        for( int i=1;i<=n;i++ ) ans=(ans+dp[n][i])%mod;
        printf("%d\n",ans);        
    }
}