Какой правильный подход для решения SPOJ DIEHARD?
Я пытался решить вопрос практики на SPOJ https://www.spoj.pl/problems/DIEHARD/ .
Однако и мой жадный подход привел к неправильному ответу, и рекурсия была слишком медленной для худшего случая. Кто-нибудь может сказать, как решить эту проблему? Я ищу кого-то, чтобы указать мне в правильном направлении.
Игра проста. Изначально у вас есть количество здоровья «H» и количество брони «A». В любой момент вы можете жить в любом из трех мест — огонь, вода и воздух. После каждого единичного времени вы должны сменить место проживания. Например, если вы в настоящее время живете в огне, вы можете войти в воду или в воздух.
- Если вы выходите в воздух, ваше здоровье увеличивается на 3, а броня увеличивается на 2
- Если вы заходите в воду, ваше здоровье уменьшается на 5, а броня уменьшается на 10
Если вы вступаете в огонь, ваше здоровье уменьшается на 20, а броня увеличивается на 5Если ваше здоровье или броня становится <= 0, ты умрешь мгновенно
Найдите максимальное время, которое вы можете выжить.
Входные данные:
Первая строка состоит из целого числа t — количества тестов. Для каждого тестового случая будет два натуральных числа, представляющих начальное здоровье H и начальную броню A.
Выход:
Для каждого теста найдите максимальное время, которое вы можете выжить.
Решение
Вот еще один способ сделать это аналитически:
a = number of times visiting air state
F = number of times visiting fire state
W = number of times visiting water state
M = a + F + W // total moves
// positive
a >= 0
F >= 0
W >= 0
// because of the restriction of moving between states...
a <= F + W + 1
F <= W + a + 1
W <= a + F + 1
// the effect of armor and health...
H < -3a + 5H + 20F
A < -2a + 10W - 5F
Максимизируйте M. Вы можете сделать это с помощью бинарного поиска M или использовать линейное программирование.
Цикл двоичного поиска:
int ok = 0;
int impossible = 1000000000;
while (impossible - ok > 1)
{
int candidate = ok + (impossible-ok) / 2;
if (check(candidate))
ok = candidate;
else
impossible = candidate;
}
return ok;
В любом случае используйте базовую алгебру средней школы, чтобы упростить неравенства / уравнения.
Другие решения
Хорошо, во-первых, попробуйте решить это жадным подходом.
Очевидно, что воздух — лучший выбор из возможных, так как он увеличивает броню и здоровье, но вы можете выходить в воздух только попеременно. Таким образом, каждый странный (то есть 1,3,5 …) ход будет в воздухе. Теперь мы должны решить, что делать с четными ходами?
Таким образом, у нас есть два варианта: огонь или вода? Мы должны быть разумными и выбирать такой ход, который удерживает H и A выше 0. Теперь прыжок в огне стоит здоровья -20, хотя это увеличивает броню на 5, но эй, подождите, какая польза от усиленной брони, если вы не ваше здоровье> 0. Поэтому, если H> 5 и A> 10, выберите воду.
А что если нам не хватает доспехов, но у нас достаточно здоровья? В этом случае у нас нет другого выбора, кроме как прыгнуть в огонь.
Так что теперь у нас есть жадный подход:
Итак, если у нас будет достаточно H и A, мы пойдем в воду.
Иначе, если H достаточно и A недостаточно, идите в огонь.
Остальное, все кончено!
Вот идеальная ссылка на реализацию:
http://ideone.com/rkobNK
#include<stdio.h>
int main(){
long long int x,i,a,b,t,h,arm;
scanf("%lld",&x);
for(i=0;i<x;i++){
scanf("%lld %lld",&a,&b);
if(a==0||b==0)
printf("0\n");
else{
t=1;
h=a+3;
arm=b+2;
while(1){
if(h>5&&arm>10){
h=h-2;
arm=arm-8;
t=t+2;
}else if(h>20&&arm<=10){
h=h-17;
arm=arm+7;
t=t+2;
}else {
printf("%lld\n",t);
break;
}
}
}
}
return 0;
}
Вы пробовали DFS? Состояние — это кортеж (воздух | огонь | вода, Н, А). Это имеет:
3 * 1000 * 1000 = 3,000,000 game states
Сделайте на нем DFS и найдите самые высокие ходы. (т.е. установите все в -1 и начальные состояния в 0, затем DFS из 0 состояний во все достижимые позиции)
Я сделал с помощью динамического прогамминга.
Dp [здоровье] [броня] [воздух / огонь / вода] — это максимальное время, которое вы можете прожить, если начнете с этого состояния
тогда текущие условия просто становятся
Dp [здоровье] [броня] [воздух / огонь / вода] = 1 + максимум следующих состояний, в которые вы можете перейти
Очевидно, что базовый случай — это когда он может уйти в никуда, поэтому ответ на этот вопрос становится нулевым.