题意略。
还可以的一道题目= =只是模型太经典之前做过同类型的，直接设f[i][j]表示前i个，j表示第i个的相对大小，根据I D或者?来分来讨论，具体看code。。
由于每次一更新，我要枚举i，还要枚举j，还由于是方案数，所以是累加起来的，暴力是n^3，所以用前缀和优化一下，去掉一个n，就是n^2的了。
dalao们都打得好短啊。
#include <cstdio> #include<cstring> #include<algorithm> #include<cstdio> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=2e3+5; char s[N]; int f[N][N],sum[N][N]; const int mo=1e9+7; int main() { scanf("%s",s+1); int n=strlen(s+1); memset(f,0,sizeof(f)); memset(sum,0,sizeof(sum)); f[1][1]=sum[1][1]=1; fo(i,2,n+1) { //int pos=i-1;//zheng int pos=n+1-i+1;//fan fo(j,1,i) { if(s[pos]=='D') { if(j==1)f[i][j]=0; else f[i][j]=(f[i][j]+sum[i-1][j-1])%mo; } else if(s[pos]=='I') { if(j==i)f[i][j]=0; else { f[i][j]=(f[i][j]+sum[i-1][i-1])%mo; f[i][j]=(f[i][j]-sum[i-1][j-1])%mo; f[i][j]=(f[i][j]+mo)%mo; } } else f[i][j]=(f[i][j]+sum[i-1][i-1])%mo; } fo(j,1,i) sum[i][j]=(sum[i][j-1]+f[i][j])%mo; } printf("%d\n",sum[n+1][n+1]); return 0; }