题目大意
解题思路
动态规划，设f[i][j]表示填到第i位，之前有j个比当前位大，自行脑补转移方程即可，最好滚动数组。
code
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int max(
int x,
int y){
return (x>y)?x:y;}
int min(
int x,
int y){
return (x<y)?x:y;}
int const mn=
1e4+
9,mo=
1e9+
7;
int n;
LL f[mn],su[mn],sd[mn];
char s[mn];
int main(){
freopen(
"d.in",
"r",stdin);
freopen(
"d.out",
"w",stdout);
scanf(
"%s",s+
1);n=
strlen(s+
1);
f[
0]=
1;
su[
0]=f[
0];
fo(j,
1,n)su[j]=(su[j-
1]+f[j])%mo;
sd[n]=f[n];
fd(j,n-
1,
0)sd[j]=(sd[j+
1]+f[j])%mo;
fo(i,
1,n){
fo(j,
0,n)f[j]=
0;
if(s[i]==
'I'){
fo(j,
0,i-
1)f[j]=sd[j];
}
else if(s[i]==
'D'){
fo(j,
1,i)f[j]=su[j-
1];
}
else{
fo(j,
0,i)f[j]=su[i];
}
su[
0]=f[
0];
fo(j,
1,n)su[j]=(su[j-
1]+f[j])%mo;
sd[n]=f[n];
fd(j,n-
1,
0)sd[j]=(sd[j+
1]+f[j])%mo;
}
printf(
"%lld",su[n]);
return 0;
}
