Concerts Gym - 101669A DP

제목 링크 제목 대의: 26개의 알파벳과 다음 알파벳의 간격을 주고 최대 일치수를 물어본다.Input: 2 10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 AB(범위 3 e2) ABBBABB(1e5) Output: 10 사례 분석: (1, 3), (1, 4), (1, 5), (1, 7), (1, 8), 9), (1, 10), (6, 8), (6, 9), (6, 9), (6, 10) (6, (6, 10) 처음에 생각해 봤는데 범위가 [35dpe]가 안 된다고 생각했다[15dpe].나중에 선배가 dp라고 해서 자기가 진지하게 생각해 봤는데 이수조가 없으면 이렇게 크게 생각할 수 없을까 하고 잘못된 생각을 했다.잘못된 사고방식: dp[i][j]i는str1에서 i까지의 위치와str2에서 j까지의 일치수를 나타낸다. 어디가 틀렸을까. 나의 일치수는str1[i]로 끝나는 일치수를 기록했을 뿐, i+1을 찾을 때 되돌아갈 때 적게 찾는다.정확한 사고방식: dp[i][j]는 j라는 위치를 기록하고str1[1~i]와 일치하는 수량을 기록한다.str1[i]=str2[j]일 때 dp[i][j]=dp[i][j-1]+dp[i-1][j-data[str1[i-2]-'A];같지 않으면 이전의 개수 dp[i][j-1]를 계승한다.코드

#include 
using namespace std;

const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
long long dp[5][maxn];
int data[30];
char str1[maxn], str2[maxn];

int main()
{
    int n, k;
    scanf("%d %d", &k, &n);
    for(int i = 0; i < 26; i++)
    {
        scanf("%d", &data[i]);
        data[i]++;
    }

    scanf("%s %s", str1, str2);
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        dp[1][i + 1] = dp[1][i] + (str1[0] == str2[i]);
        dp[1][i + 1] %= mod;
    }
    for(int i = 2; i <= k; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i%2][j] = dp[i%2][j-1];
            if(str1[i - 1] == str2[j - 1])
            {
                if(j - (data[str1[i - 2] - 'A']) >= 0)
                {
                    dp[i%2][j] += dp[(i - 1)%2][j - (data[str1[i - 2] - 'A'])];
                    dp[i%2][j] %= mod;
                }
            }
        }
    }

    printf("%lld
", dp[k % 2][n]);

}

/*
3 29
2 3 5 2 3 3 2 5 2 3 5 3 5 5 5 2 1 4 1 2 3 2 3 1 5 2
PVZ
PPZIWADMJVRVHRTBKJZKUXOZZSAZM
answer :16
*/

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

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

poj 간단한 dp문제 몇 개

제목:poj1836 제목: 수열을 먼저 점차적으로 늘린 다음에 점차 줄이는 형식을 구하려면 빼야 할 숫자 개수를 구한다.물론 직접 체감하거나 체감하기만 하고 체감하지 않을 수도 있다.분석: 가장 긴 점증자 서열의 방...

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

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

Concerts Gym - 101669A DP

좋은 웹페이지 즐겨찾기