Concerts Gym - 101669A DP

4108 단어 단순
제목 링크 제목 대의: 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 */

좋은 웹페이지 즐겨찾기