【GDOI2018模拟7.10】B

Description

Input

Output

一个整数表示答案

Sample Input

?D

Sample Output

3

Solution

显然DP 设 f[i][j] 表示到第i位，这一位数第j小的方案数 转移显然，难点就是想到是第j小而不是数字选j

Code

#include<cstdio> #include<algorithm> #include<cstring> #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 N 1010 #define mo 1000000007 using namespace std; int n,bz[N]; long long ans=0,f[N][N]; char s[N]; int main() { scanf("%s",s+1); n=strlen(s+1); f[n+1][1]=1; fd(i,n,1) { int l=n-i+2; fo(j,1,l) { if(s[i]=='D') { f[i][j]=f[i+1][j-1]; } if(s[i]=='I') f[i][j]=(f[i+1][l-1]-f[i+1][j-1]+mo)%mo; if(s[i]=='?') f[i][j]=f[i+1][l-1]; f[i][j]=(f[i][j]+f[i][j-1])%mo; } } printf("%lld",f[1][n+1]); }