[59测试]B

题目描述

对于一个排列，考虑相邻的两个元素，如果后面一个比前面一个大，表示这个位置是上升的，

用 I 表示，反之这个位置是下降的，用 D 表示。如排列 3,1,2,7,4,6,5 可以表示为 DIIDID。

现在给出一个长度为 n-1 的排列表示，问有多少种 1 到 n 的排列满足这种表示。

输入输出格式

输入格式

一个字符串 S，S 由 I，D，？组成。？表示这个位置既可以为 I，又可以为 D。

输出格式

有多少种排列满足上述字符串。输出排列数模 1000000007。

输入输出样例

输入样例1

?D

输出样例1

3

说明

对于 20%的数据，S 长度 ≤ 10；

对于 100%的数据，S 长度 ≤ 1000。

思路

dp

f[i][j]:前i个数中,最后一位是第j大的;

• I:第i位的j比上一位大：由$$\sum f[i-1]k$$推出；因为有可能 j 数字在之前填过了，但是不影响结果，因为我们可以认为所有填的$$\geq j$$的数字都+1，保证了情况的全面性（即前 i 位可以填$$> i$$的数字）。

• D:第 i 位的 j 要比上一位小，由$$\sum f[i-1]k$$推来; 同理：j 数字也可能填过了，也可以认为+1.

• ?:以上方案相加

代码

滚动数组优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 1000000007
#define ll long long
using namespace std;
ll dp[5][1005],idx=1,cur=0,ans;
int main()
{
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    char c=getchar();
    dp[0][1]=1;
    while (c=='I'||c=='D'||c=='?')
    {
        cur^=1;idx++;
        for (int i=1;i<=idx-1;i++)
          {
            dp[cur^1][i]+=dp[cur^1][i-1]%M;
            dp[cur][i]=0;
          }
        if (c!='D'){
            for (int i=2;i<=idx;i++)
              dp[cur][i]=dp[cur^1][i-1]%M;
        }
        if (c!='I'){
            for (int i=1;i<idx;i++)
              dp[cur][i]+=((dp[cur^1][idx-1]-dp[cur^1][i-1])%M+M)%M;
        }
        c=getchar();
    }
    for (int i=1;i<=idx;i++)
     ans=(ans+dp[cur][i])%M;
    cout<<ans;
    return 0;
}

前缀和优化

#include <bits/stdc++.h>
using namespace std;

const int MOD=1e9+7;
const int MAXNUM=1000+5;
int f[MAXNUM][MAXNUM];
int Sum[MAXNUM][MAXNUM];
char s[MAXNUM];

int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    memset(f,0,sizeof(f));
    memset(Sum,0,sizeof(Sum));
    f[1][1]=1;Sum[1][1]=1;
    for(int i=2;i<=n+1;i++)
        {
            int cur=n+2-i;
            for(int j=1;j<=i;j++)
            {
                if(s[cur]=='D')
                {
                    if(j==1)
                        f[i][j]=0;
                    else
                        f[i][j]=(f[i][j]+Sum[i-1][j-1])%MOD;
                }
                else if(s[cur]=='I')
                {
                    if(j==i)
                        f[i][j]=0;
                    else
                    {
                        f[i][j]=(f[i][j]+Sum[i-1][i-1])%MOD;
                        f[i][j]=(f[i][j]-Sum[i-1][j-1])%MOD;
                        f[i][j]+=MOD;
                        f[i][j]%=MOD;
                    }
                }
                else
                {
                    f[i][j]=(f[i][j]+Sum[i-1][i-1])%MOD;
                }
            }
            for(int j=1;j<=i;j++)
                Sum[i][j]=(Sum[i][j-1]+f[i][j])%MOD;
        }
        printf("%d\n",Sum[n+1][n+1]);
    }
}