zoj 3543 Number String

zoj  3543 Number String
이 문제를 풀었다. 하룻밤 동안 다른 사람들은 아주 적은 dp라고 말했지만, 풀지 못했다. 보아하니 확실히 약해진 것 같다......TT, 인터넷 결산 보고서는 개인이 말한 것이 모두 명확하지 않고 세부적인 것에 대해서도 명확하게 설명하지 못했다. 여기서 만약에 요리가 제 개인적인 이해를 이야기한다면...
만약에 제목이 요구하는 서열이 n의 한 배열이 아니라 n개의 수라면 각 수의 범위는 [1,n]에 있다. 주어진 점차적인 점차적인 점차적인 서열에 부합되는 서열이 얼마나 되는지 구하면 제목이 쉽겠지?생각하지 마세요. 상태는 dp[len][i]를 나타내고 길이는 len을 나타내며 끝의 숫자는 i의 서열의 개수를 나타냅니다.직접 O(n^2)로 만들 수 있어요...그런데 이 문제는 1, 2,...n의 전체 배열, 이렇게 하면 분명히 안 된다.
상태는 dp[len][i]로 길이를 표시하고 끝의 숫자는 i의 서열의 배열 개수를 나타낸다. 이렇게 i의 수치 범위는 [1,len]이다. 만약에 n=len+1이 맞다면 i의 수치 범위는 [1,len+1]이다. 이때 i의 수치가 <=len이고 이전의 배열 후에 i를 더하면 안 된다. 왜냐하면 이 서열은 배열이 아니기 때문이다(두 개의 i가 있다). 그러나 원래 배열된 i 이후의 수를 모두 +1을 더하면 안 된다.그러면 이렇게 하면 조건에 부합된다. 예를 들어 원래 서열은'12'이었는데 지금은 그 다음에 1을 더하면'12'->'23', 그리고 1을 더하면'231'이다.이 점을 알면'231'이 합법적인 배열임을 보증한다. 다른 것은 모두 간단하다
PS: 처음에 롱롱을 두 번 사용했는데 여기 int, 1000+ms가 지나갔어요.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int mod=1000000007;
typedef long long ll;
char s[1010];
int dp[1020][1020],sum[1020][1020];

int main()
{
    while(scanf("%s",s+2)==1)
    {
        int len=strlen(s+2);
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        dp[1][1]=sum[1][1]=1;
        for(int i=2;i<len+2;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(s[i]=='I'||s[i]=='?')
                   dp[i][j]=sum[i-1][j-1];
                if(s[i]=='D'||s[i]=='?')
                   dp[i][j]=(dp[i][j]+sum[i-1][i-1]-sum[i-1][j-1])%mod;
                sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
            }
        }
        int ans=0;
        for(int i=1;i<=len+1;i++)
          ans=(ans+dp[len+1][i])%mod;
        printf("%d
",(ans%mod+mod)%mod);
    }
    return 0;
}