- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 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 ;)
Follow us!
Хотя, возможно, я просто невнимательно смотрел
у динамики всегда решение изящное, взять даже ДП по изломанному профилю, но в ехать в него даже и с условием сложновато
если твой символ равен Y и смотришь ты две строки, i и j и новое полученное решение выгоднее старого, то переприсваеваешь его обратно, реккуретной формулой красиво выглядет. только я в этом гомнокода не вижу, т.к. и сам в ACM участвую :)
решение верное, сданное.
это я компилил g++-ом.
И не забываем про "#include <cstdio>"
Не вижу нигде правил, чтоб к Си разделу говнокода относился только С89, без С99. В Си раздел даже Objective-C спихивают и ничего...
да, обжектив с скомпилит С89 но не наоборот.
Голосуем за новый раздел?
Это от безысходности. Раздел был бы соответствующий так при ошибке публикации пестрило бы все сообщениями "где здесь Obj-c", "где здесь С" и пр.
А популярность Obj-C хоть и растет (Джобс постарался), но кода, хотя бы даже здесь, на нем ещё несравнимо мало с теми же С/С++. Может и раздела поэтому нет. Хз.
А по поводу Objective-C, я что-то не понял, а куда вы предлагаете спихивать код от Objective-C, в "куча" что ли?
А вот на cstdio действительно не обратил внимания, виноват.