Блог пользователя Medina

Задача "Сумма цифр" (на динамику). Как хранить наименьшее число?
Автор Medina, 12 лет назад, По-русски

http://acm.timus.ru/problem.aspx?space=1&num=1658 я сделала dp[s1][s2], где s1 сумма цифр, а s2 сумма квадратов, а в dp[s1][s2] хранила наименьшую длину числа и востановливала ответ. Но увы, она не всегда правильно работает, то есть можно подобрать числа такой же длины, что соответствуют тем же условиям, но меньше чем мой ответ. Как это исправить?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а если хранить не длину, а само число?

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Я вводил дополнительную размерность динамики — минимальная последняя цифра числа.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

можно восстанавливать цифры по одной слева направо. т.е. пытаемся поставить сначала 1, если dp[s1-1][s2-1]+1=dp[s1][s2] тогда единицу можно поставить, делаем это и переходим к следующей цифре. Если нет то пробуем поставить 2, т.е. если dp[s1-2][s2-2*2]+1=dp[s1][s2], тогда можно, иначе — нет. Таким образом, мы каждый раз выбираем минимально возможную цифру и поэтому ответ будет лексикографически наименьшим.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    я что-то не до конца поняла. Хотите скз, что 1 или 2 надо пробовать в начало числа ставить?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      пробуете все цифры подряд(в порядке увеличения), как только полуилось — берете.

      → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, именно так, если мы можем поставить какую-то цифру и длина оставшейся части на единицу меньше текущей, то это значит, что есть способ достроить число до конца. А с начала цифры ставить нужно для того, чтобы число получалось как можно меньше.

      → Ответить