[NOIP2015] 꼬치

전송문은 경기장에서 이 문제로 인해 많은 시간을 망쳤다.... 아니면 내가 너무 형편없었지만 그래도 잘 썼다.DP의 사고방식은 매우 간단하다. f(k, i, j)는 k단을 나누고 첫 번째 줄의 앞의 i개의 숫자를 사용해서 두 번째 줄의 앞의 j개의 방안수를 구성했다.
f(k, i, j) = ∑f(k-1, l, j-1) ∑f(k-1, l, l, l, j-1) ∑f(k-1, l, j-1) + f(k, i-1, j-1)는 s1[i]==s2[j]이고 s1[i-1]!s2[j-3-1]가 s1[i]==s2[j]이고 s1[i-3-1]==s2[j-31]에서 0첫 번째 이전은 독립적으로 한 부분을 개척할 가능성수이고, 두 번째 이전부터 k개 부분을 나누어 k개 부분을 확대하는 방안수를 포함한다.역시 이해하기 쉽다. 물론 f수 그룹은 1차원으로 굴러야 한다. 그렇지 않으면 메모리가 폭발할 것이다.
나는 이 문제의 난이도가 모두 그 당시의 거북이 바둑과 당시의 난이도와 많이 다르지 않다고 생각한다.그런데 이 문제의 70점 알고리즘은
O(nm2k)는 쓰기가 쉬워서 차이가 안 나요.
제 컨디션이 바뀌는 걸 보고 생각해 낼 수 있을 거라고 믿습니다.
O(nmk) 방법.사실 저희가 지켜야 할 건 그거밖에 없어요.
∑tmp수 그룹으로 저장하면 됩니다(코드 참조)
코드

#include
#include
typedef unsigned int LL;
const LL MOD = 1000000007LL;
const int MAXN = 1005;
int n, m, K;
LL f[2][MAXN][205];
LL tmp[2][MAXN][205];
char s1[MAXN], s2[MAXN];
LL ans = 0;
int main()
{
    scanf("%d%d%d", &n, &m, &K);
    scanf("%s%s", s1+1, s2+1);
    f[0][0][0] = 1;
    tmp[0][0][0] = 1;
    for(int i = 0; i <= n; i ++)
        tmp[0][i][0] = 1;
    for(int k = 1; k <= K; k ++) {
        memset(tmp[k&1], 0, sizeof (tmp[k&1]));
        memset(f[k&1], 0, sizeof (f[k&1]));
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                if(s1[i] == s2[j]) {
                    f[k&1][i][j] = tmp[(k+1)&1][i-1][j-1];
                    if(s1[i-1] == s2[j-1]) f[k&1][i][j] = (f[k&1][i][j] + f[k&1][i-1][j-1]) % MOD;
                    if(f[k&1][i][j] >= MOD) f[k&1][i][j] -= MOD;
                }
                tmp[k&1][i][j] = (tmp[k&1][i][j] + f[k&1][i][j]) % MOD + tmp[k&1][i-1][j];
                if(tmp[k&1][i][j] > MOD) tmp[k&1][i][j] -= MOD;
            }
        }
    }
    for(int i = 1; i <= n; i ++)
        ans = (ans + f[K&1][i][m]) % MOD;
    printf("%d
", ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[noip2013] 꽃장인DP||욕심

화공의 동채에 한 줄의 꽃을 심었는데, 꽃마다 모두 자신의 높이가 있다.꽃은 자랄수록 커지고 비좁아진다.동동은 이 줄의 일부 꽃을 옮기고 나머지는 제자리에 남겨 남은 꽃이 자랄 수 있는 공간을 마련하기로 했다. 또한...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[NOIP2015] 꼬치

좋은 웹페이지 즐겨찾기