Jokser's blog

By Jokser, 9 years ago, In Russian,

Задача A

Здесь все просто. Если число нечетное или равно 2, то ответ "NO", иначе ответ "YES".

Задача B

В этой задаче есть более простые пути решения, но я решил написать ДП. Обозначим массивом bool dp[d][sumTime] возможность того, что в день d можно набрать ровно sumTime времени. Если true - то можно, если false - то нельзя. Изначально dp[0][0]=true, остальные - false.

Получаем следующее реккурентное соотношение dp[i][j]=dp[i-1][j-k], где i - текущий день, j - текущее суммарное время и k - время, которое Петя хочет потратить в i день.

Попутно запоминаем расписание формулой from[i][j]=k. Далее, восстановить расписание не составляет труда.

Задача C

Здесь можно использовать map<string,int> в С++. Считываем имя, смотрим какое число соответствует данному имени. Если 0 - выводим OK, и прибавляем единичку в map. Иначе выводим имя+текущее число в mapе и снова прибавляем единичку в map.

Задача D

Сначала отсортируем все конверты, включая открытку по возрастанию по ширине. Далее применяем алгоритм, как если бы мы искали самую длинную возрастающуюю подпоследовательность. Обозначаем dp[i] - длину наибольшой цепочки конвертов, оканчивающейся на конверт с номером i. Тогда получаем следующее реккурентное соотношение.

dp[i]=max(dp[i],d[j]+1), где j=0..i-1 и a[i].длина>a[j].длина и a[i].ширина>a[j].ширина.

Начальное условие dp[номер открытки]=0. Все остальным можно сделать -1.

Запоминаем максимальное число открыток, а также порядок их следования.

Далее отсортируем все конверты, включая открытку по возрастанию, но теперь уже по длине! И проделываем все те же действия, что написаны выше. Cравниваем результаты и выводим наибольший.

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it