Description
Solution
其实这是一道很简单的题目，但是想法非常的机智。 很显然有一个DP方程设f[i][j]表示前i个只填前i个数，最后一个数是j的方案数。 我们想一想怎样把i+1放进去且使得它合法且不重复不遗漏。 在排列的问题上很显然有一个方法是把i+1插入到前面去，但是这样不一定合法且位置不好找。我们可以知道前面f[i]的状态全都是1~i的排列，如果我们现在最后一位要放j，那么把大于等于j的数同时+1，就可以把i+1插进去了且合法。 所以我们现在可以对最后面那个位置的字符分类讨论一下。 转移到i+1 如果是U那么既然要填j，就可以由f[i][1~j-1]转移过来。 如果是I那么既然要填j，因为大于等于j的都要加1（要是+1后都>j的数），所以可以由f[i][j~i]转移过来 如果是？那么两个加起来。 所以再维护一个前缀和就好了。
Code
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=
1007,mo=
1e9+
7;
ll i,j,k,l,t,n,m;
char s[maxn];
ll f[maxn][maxn],g[maxn][maxn],ans;
int main(){
scanf(
"%s",s+
1);n=
strlen(s+
1);
f[
1][
1]=
1;g[
1][
1]=
1;
fo(i,
1,n){
fo(j,
1,i+
1){
if(s[i]==
'D'||s[i]==
'?'&&i>=j)f[i+
1][j]=(f[i+
1][j]+g[i][i]-g[i][j-
1])%mo;
if(s[i]==
'I'||s[i]==
'?')f[i+
1][j]=(f[i+
1][j]+g[i][j-
1])%mo;
g[i+
1][j]=(g[i+
1][j-
1]+f[i+
1][j])%mo;
}
}
ans=g[n+
1][n+
1];ans=(ans+mo)%mo;
printf(
"%lld\n",ans);
}
