Description

n<=1000

Analysis

省选组的一道水题 模型看起来要么dp要么分治的嘛，然后我一开始是想的分治，?隔开许多个块，然后每个块互不影响，单独处理 但是处理也要dp啊，还不如直接dp 容易发现，真实值不重要也不必要，重要的是相对大小 设 f[i][j] 表示确定完前 i 个数，第i个在前 i 个里从小到大排第j的方案数 转移显然，可以用前缀和优化 O(n^2)

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define efo(i,v) for(int i=last[v];i;i=next[i]) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; typedef long long ll; const int N=1005,mo=1e9+7; int n,f[N][N],pre[N][N]; char s[N]; int main() { scanf("%s",s+1); n=strlen(s+1); f[0][1]=pre[0][1]=1; fo(i,1,n) { fo(j,1,i+1) if(s[i]=='I') (f[i][j]+=pre[i-1][j-1])%=mo; else if(s[i]=='D') f[i][j]=((f[i][j]+pre[i-1][i]-pre[i-1][j-1])%mo+mo)%mo; else (f[i][j]+=pre[i-1][i])%=mo; fo(j,1,i+1) pre[i][j]=(pre[i][j-1]+f[i][j])%mo; } printf("%d",pre[n][n+1]); return 0; }