Кресты / Говнокод #3762 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
#include <cstdio>
#include <memory.h>

#define maxn 18

char c[maxn][maxn];
int d[1 << maxn];

int main()
{
  freopen("network.in", "rt", stdin);
  freopen("network.out", "wt", stdout);
  
  int n; scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%s", c[i]);
    
  memset(d, 0, sizeof(d));
  
  for (int k = 0; k < (1 << n); k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (c[i][j] == 'Y' && k & (1 << i) && k & (1 << j) && d[k - (1 << i) - (1 << j)] + 2 > d[k])
          d[k] = d[k - (1 << i) - (1 << j)] + 2;
          
  int max = 0;
  for (int i = 0; i < (1 << n); i++)
    if (d[i] > max)
      max = d[i];
      
  printf("%d\n", max);
  
  return 0;
}

ACM-задачка на динамику по подмножествам.
Кто поймет, тому 5 ;)

Запостил: ystepanov ystepanov, (Updated )

Комментарии (22) RSS

  • ava xaionaro # Ссылка на оригинал 0

    Честно говоря очень лень вглядываться в данный if, т.к. я обычно заглядываю на govnokod.ru чтобы расслабить мозг, а не напрячь его, но поверхностным взглядом кажется подозрительным "d[k - (1 << i) - (1 << j)]", т.к. допустим, если k==0x10, i==4, j==4 и c[4][4]=='Y', то тогда будет производится попытка считать d[0x10 - 0x10 - 0x10] === d[-0x10], что выходит за рамки "int d[1 << maxn]".

    Хотя, возможно, я просто невнимательно смотрел
    Ответить

    • ava ystepanov # Ссылка на оригинал 0 ⇈

      прошу прощения, исходя из условия задачи, c[i][i] не может равняться 'Y' 🙂
      Ответить

  • ava daemon_master # Ссылка на оригинал 0

    пойми решение без условия, хм, интересно
    у динамики всегда решение изящное, взять даже ДП по изломанному профилю, но в ехать в него даже и с условием сложновато

    если твой символ равен Y и смотришь ты две строки, i и j и новое полученное решение выгоднее старого, то переприсваеваешь его обратно, реккуретной формулой красиво выглядет. только я в этом гомнокода не вижу, т.к. и сам в ACM участвую 🙂
    Ответить

    • ava daemon_master # Ссылка на оригинал 0 ⇈

      тогда решение становится понятным, динамикой перебор всех пар компьютеров между собой, ты своим k перебираешь битовые маски, i, j соответсвенно компьютеры. Если они могут между собой обмениваться c[i][j] == 'Y', то проверяешь затем битовой операцией входит ли твой i-ый компьютер в битовую маску и входит ли в неё j-ый компьюетр, если входят, то смотришь, своё предыдущее найденное решение без i и без j + пара текущих (+2) выгоднее того, что сейчас хранится в k'ой ячейке? если же да, то заменяешь, затем ищешь в массиве своём d максимум. решение красивое, молодец
      Ответить

      • ava ystepanov # Ссылка на оригинал 0 ⇈

        написано методом "нужно написать как можно быстрее и чтобы работало" 🙂 + 23 строчка все-таки не слишком айс 🙂
        Ответить

        • ava daemon_master # Ссылка на оригинал 0 ⇈

          а как по-другому решать на олимпиадах? если задача прошла все тесты, то уже нечего тут останавливаться, ибо время идёт )
          Ответить

    • ava ystepanov # Ссылка на оригинал 0 ⇈

      разницы особой нет тут, чем компилить - сяшным компилером или ++овым.
      это я компилил g++-ом.
      Ответить

    • ava Altravert # Ссылка на оригинал 0 ⇈

      И я не буду: его здесь нет. Вот так вот быстро закрыли тему, продуктивненько так, ага?
      Ответить

    • ava xaionaro # Ссылка на оригинал 0 ⇈

      Я уже примерно в 10-ый раз повторяю, что для Си обычно используют стандарт С89, в котором нельзя определять переменные внутри for(...)!

      И не забываем про "#include <cstdio>"
      Ответить

      • ava Говногость # Ссылка на оригинал 0 ⇈

        >что для Си обычно используют стандарт С89
        Не вижу нигде правил, чтоб к Си разделу говнокода относился только С89, без С99. В Си раздел даже Objective-C спихивают и ничего...
        Ответить

        • ava da4ever # Ссылка на оригинал 0 ⇈

          а вот это, к стати, совсем не правильно!
          да, обжектив с скомпилит С89 но не наоборот.
          Голосуем за новый раздел?
          Ответить

        • ava absolut # Ссылка на оригинал 0 ⇈

          > В Си раздел даже Objective-C спихивают и ничего...
          Это от безысходности. Раздел был бы соответствующий так при ошибке публикации пестрило бы все сообщениями "где здесь Obj-c", "где здесь С" и пр.
          А популярность Obj-C хоть и растет (Джобс постарался), но кода, хотя бы даже здесь, на нем ещё несравнимо мало с теми же С/С++. Может и раздела поэтому нет. Хз.
          Ответить

        • ava xaionaro # Ссылка на оригинал 0 ⇈

          Я и не говорил, что данный код нельзя запихать в раздел Си из-за тех определений переменных, я объясняю почему этот код имеет право быть в разделе C++. А по поводу стандартов тут вопрос философский, т.к. их можно вводить сколько угодно с какими угодно причудами, т.ч. есть смысл рассортировывать код с расчётом лишь на общепринятые и общеиспользуемые стандарты. Но повторюсь, я лишь отвечаю на вопрос, почему данный код может быть закинуть в раздел C++, т.е. я не доказываю, что данный код нельзя запихать в раздел Си (что и доказывать это не надо из-за "cstdio").

          А по поводу Objective-C, я что-то не понял, а куда вы предлагаете спихивать код от Objective-C, в "куча" что ли?
          Ответить

      • ava koodeer # Ссылка на оригинал 0 ⇈

        Си - это Си. Неважно, какого года стандарт.
        А вот на cstdio действительно не обратил внимания, виноват.
        Ответить

        • ava xaionaro # Ссылка на оригинал 0 ⇈

          Я и не говорил, что C99 - это не Си. Я просто пояснял, почему данный код можно положить в C++. Всё-таки стоит признать, что общеиспользуемые стандарты определяют традиции.
          Ответить

Добавить комментарий

Семь раз отмерь — один отрежь, guest!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓