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);
}
} 2020HDU暑假多校赛补题 文章被收录于专栏
菜的一批
曼伦商贸公司福利 94人发布
查看5道真题和解析
