ZOJ 3543 넘버 스트링 [2011 다롄 지역 경기][dp]
2186 단어 Start_동적 기획
한 꿰미를 D, I,?구성된 길이가 n인 문자열은 어떤 규칙을 만족시키는 1부터 n+1까지의 배열 집합을 나타낸다. D는 이 위치의 숫자가 앞의 숫자보다 작다는 것을 의미하고 I는 이 위치의 숫자가 앞의 숫자보다 크다는 것을 의미하는가?불확정
예컨대
DI를 만족시키는 숫자 배열은 3, 1, 2, 1, 3.
1<=n<=1000, 이 조건을 충족시키는 문자열 몇 가지를 구합니다
디자인의 dp는 다음과 같다
dp[i][j]는 상기 문자열을 만족시키기 전 i-1항의 길이가 i꼬리가 j인 1부터 i까지의 배열수를 나타낸다
i-1 항목이 D인 경우
dp[i][j]=sigma(dp[i-1][k]),i-1=>k>=j
i-1 항목이 I인 경우
dp[i][j]=sigma(dp[i-1][k]),j>k>=1
마지막으로sigma(dp[n+1][k]), 1<=k<=n+1 출력
왜 이러는지, 왜냐하면 1부터 i-1까지의 배열 뒤에 j가 적혀 있을 때, 앞에 i-1의 수가 j와 같은 수보다 크면 모두 1을 더하면 새로운 1부터 i까지의 배열을 얻을 수 있기 때문이다.
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
const LL MOD=1000000007;
char str[2222];
LL dp[1111][1111];
LL sum[1111][1111];
int main(){
#ifndef ONLINE_JUDGE
freopen("H:/in.txt","r",stdin);
#endif // ONLINE_JUDGE
while(scanf("%s",str+2)!=EOF){
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
dp[1][1]=1;
sum[1][1]=1;
LL len=strlen(str+2);
for(LL i=2;i<2+len;i++){
for(LL j=1;j<=i;j++){
if(str[i]=='D' || str[i]=='?'){
dp[i][j]+=sum[i-1][i-1]-sum[i-1][j-1];
dp[i][j]=(dp[i][j]+MOD)%MOD;
}
if(str[i]=='I' || str[i]=='?'){
dp[i][j]+=sum[i-1][j-1];
dp[i][j]=(dp[i][j]+MOD)%MOD;
}
sum[i][j]=(sum[i][j-1]+dp[i][j])%MOD;
}
}
LL ans=0;
for(LL i=1;i<=len+1;i++) ans=(ans+dp[len+1][i])%MOD;
printf("%lld
",ans);
}
return 0;
}