Description
Data Constraint
Solution
我们发现序列只要求相对大小。所以我们设dp[i][j]表示当前匹配到第i个位置，i位置上放的点的值为j的方案，同时保证前i个数放的值都∈[1,i]，每次我们枚举i-1位放什么，若当前状态为’I’，[j,i-1]所有数+1,在[1,j-1]中枚举i-1位放的数。若当前状态为’D’，同时[j,i-1]所有数+1,在[j,i-1]中枚举i-1位放的数。‘？’就结合起来。dp[i][j]+=dp[i-1][k]。由于这样搞复杂度是O(N^3)，所以我们用前缀和处理一下，变成O(N^2).
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=
1e3+
5,mo=
1e9+
7;
ll f[maxn][maxn],s[maxn][maxn];
char s1[maxn];
ll n,m,i,t,j,k,l,x,y,z;
int main(){
scanf(
"%s\n",s1+
1);n=
strlen(s1+
1)+
1;
f[
1][
1]=s[
1][
1]=
1;
for (i=
2;i<=n;i++){
for (j=
1;j<=i;j++)
if (s1[i-
1]==
'I') f[i][j]=s[i-
1][j-
1];
else if (s1[i-
1]==
'D') f[i][j]=(s[i-
1][i-
1]-s[i-
1][j-
1]+mo)%mo;
else f[i][j]=s[i-
1][i-
1];
for (j=
1;j<=i;j++)
s[i][j]=(s[i][j-
1]+f[i][j])%mo;
}
printf(
"%lld\n",s[n][n]);
}
