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

Задачка с LightOJ
Автор chrome, 11 лет назад, По-русски

Можете помочь с задачкой с LightOJ, динамика по подмножествам, я писал за O(n ^ 2 * 2 ^ n), но TLE. Removed after AC :), Задача

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

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

У меня за O(2 ^ n * n ^ 2) прошло. My code

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

не используй memset каждый раз. заполни массив используя два цикла до нужных значений.

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

    А в чем будет отличие?

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

      массив большого размера не будет каждый раз целиком обнуляться, а обнуляться будет только нужная часть. ТЛ из-за этого.

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

        Вы хотите сказать что memset обнуляет весь массив?

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

          Обнуляет столько байт, сколько в третьем параметре написано

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

          memset (d, 0, sizeof d); обнуляет весь массив. Смотри, там тесты хитрые. Если бы тебе дали 100 тестов с n = 16, то ты бы получил ТЛ. Но в мультитестовых задачах часто делают пару больших тестов и много маленьких, поэтому решение которое не обнуляет весь массив должно зайти. Кстати задача "о назначениях" имеет решение за n^3 венгерским алгоритмом или максимальным потоком минимальной стоимости.

          → Ответить