LINUX.ORG.RU

История изменений

Исправление fsb4000, (текущая версия) :

В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.

Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1

Потом обходим все подстроки и заполняем матрицу.

Вот отрывок:

// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
    x = parse_substring(full_string, len - i, len - j);
    for (k = 0; k + x <= n; k++) {
        if (dp[k + x][i] > dp[k][j] + 1)
        {
            dp[k + x][i] = dp[k][j] + 1;
        }
    // ....
    }
}

Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL

Но это не всё, дальше ещё нужно будет решить вопрос с нулями…

Если решишь, кинь потом в тему своё решение на хаскеле…

Исправление fsb4000, :

В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.

Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1

Потом обходим все подстроки и заполняем матрицу.

Вот отрывок:

// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
    x = parse_substring(full_string, len - i, len - j);
    for (k = 0; k + x <= n; k++) {
        if (dp[k + x][i] > dp[k][j] + 1)
        {
            dp[k + x][i] = dp[k][j] + 1;
        }
    // ....
    }
}

Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL

Но это не всё, дальше ещё нужно будет решить вопрос с нулями…

Исходная версия fsb4000, :

В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.

Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1

Потом обходим все подстроки и заполняем матрицу.

Вот отрывок:

x = parse_substring(full_string, len - i, len - j);
for (k = 0; k + x <= n; k++) {
    if (dp[k + x][i] > dp[k][j] + 1)
    {
        dp[k + x][i] = dp[k][j] + 1;
    }
// ....
}

Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL

Но это не всё, дальше ещё нужно будет решить вопрос с нулями…