5219. 【GDOI2018模拟7.10】B
题目大意：
考试想法：
正解：
代码：
题目大意：
现在有一个字符串
s
s
s
当
s
[
i
]
s[i]
s[i]为
I
I
I时
a
n
s
[
i
]
>
a
n
s
[
i
−
1
]
ans[i]>ans[i-1]
ans[i]>ans[i−1];
当
s
[
i
]
s[i]
s[i]为
D
D
D时
a
n
s
[
i
]
<
a
n
s
[
i
−
1
]
ans[i]<ans[i-1]
ans[i]<ans[i−1];
当
s
[
i
]
s[i]
s[i]为
?
?
?时
a
n
s
[
i
]
ans[i]
ans[i]无限制。
考试想法：
考试的时候什么也没想到，所以就打了个暴力。
正解：
考虑[ − 1] = ′′时的转移：
f[][] = ∑ f[− 1][] −1
=1 ，只需要对f维护一个前缀和即可以做到(1)地转移。
在要求为下降或者没有限制的时候同理。
代码：
#include<bits/stdc++.h>
using namespace std;
char s[1005];
long long f[1005][1005],sum[1005][1005];
int len,mod=1e9+7,ans;
int main()
{
scanf("%s",s+1);
len=strlen(s+1)+1;
f[1][1]=1;
sum[1][1]=1;
for(register int i=2;i<=len;i++)
{
for(register int j=1;j<=i;j++)
{
if(s[i-1]=='I') f[i][j]=sum[i-1][j-1];
else if(s[i-1]=='D') f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+mod)%mod;
else f[i][j]=sum[i-1][i-1];
sum[i][j]=(sum[i][j-1]+f[i][j]+mod)%mod;
}
}
printf("%lld",sum[len][len]);
return 0;
}