[UOJ#149] [NOIP2015] 하위 문자열(dp)

제목 설명

전송문

문제풀이

f(i, j, k)를 설정하면 a의 전 j 문자에서 i단을 선택하여 연결하면 b의 전 k개와 일치하는 방안 수를 나타낸다.g(i, j)는 a의 i번째 문자와 b의 j번째 문자가 뒤에서 앞으로 최대 몇 개까지 일치할 수 있는지 미리 처리할 수 있다.그러면 f(i, j, k)= ∑l=1g(i, j)f(i-3-1, j-3l, k-3l)는 dp가 3차원 상태인 것을 확신할 수 있고 O(n)전이로 시간과 공간이 모두 폭발했다.어떻게 최적화할지 고민하다.사실 최적화는 모두 비교적 간단하다.공간에서 f(i)는 f(i-1)만 관련되어 있음을 발견할 수 있으며 스크롤 그룹을 사용할 수 있습니다.시간적으로 이동할 때 연속적인 합을 추가하여 접두사와 최적화를 사용할 수 있음을 발견했다.f(i)의 2차원을 2차원 평면으로 본다면 여기 접두사와 점(x, y)은 걸을 수 없을 때까지 왼쪽으로 올라가는 점의 합이다.시간 복잡도 O (nmk).

코드

#include
#include
#include
using namespace std;
#define N 1005
#define M 205
#define Mod 1000000007

int n,m,p;
int f[2][N][M],s[2][N][M],g[N][M];
char a[N],b[M];

void init()
{
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            g[i][j]=min(i,j);
            for (int k=1;k<=min(i,j);++k)
                if (a[i-k+1]!=b[j-k+1])
                {
                    g[i][j]=k-1;
                    break;
                }
        }
}
int main()
{
    scanf("%d%d%d
",&n,&m,&p);
    gets(a+1);gets(b+1);

    init();
    for (int i=1;i<=m;++i)
        for (int j=i;j<=n;++j)
        {
            f[1][j][i]=f[1][j-1][i];
            if (g[j][i]==i) f[1][j][i]++;
            s[1][j][i]=s[1][j-1][i-1]+f[1][j][i];
        }

    for (int i=2;i<=p;++i)
    {
        memset(f[i&1],0,sizeof(f[i&1]));
        memset(s[i&1],0,sizeof(s[i&1]));
        for (int j=1;j<=n;++j)
            for (int k=1;k<=m;++k)
            {
                f[i&1][j][k]=f[i&1][j-1][k];
                if (g[j][k])
                {
                    int x=s[(i-1)&1][j-1][k-1];
                    f[i&1][j][k]=(f[i&1][j][k]+s[(i-1)&1][j-1][k-1])%Mod;
                    int J=max(j-g[j][k]-1,0),K=max(k-g[j][k]-1,0);
                    int y=s[(i-1)&1][J][K];
                    f[i&1][j][k]=((f[i&1][j][k]-s[(i-1)&1][J][K])%Mod+Mod)%Mod;
                }
                s[i&1][j][k]=(s[i&1][j-1][k-1]+f[i&1][j][k])%Mod;       
            }
    }
    printf("%d
",f[p&1][n][m]);
}