J'essayais de résoudre une question de pratique sur spoj https://www.spoj.pl/problèmes / Diehard / . Cependant, mon approche gourmande a entraîné une mauvaise réponse et une récursivité était trop lente pour le pire des cas. Quiconque dit comment aborder ce problème? Je cherche quelqu'un pour me diriger dans la bonne direction.
Le jeu est simple. Vous avez initialement une quantité de santé et «une» quantité d'armure. À tout instant, vous pouvez vivre dans l'un des trois places - feu, eau et air. Après chaque unité, vous devez changer votre lieu de vie. Par exemple, si vous vivez actuellement en feu, vous pouvez entrer dans l'eau ou l'air.
- Si vous entrez dans l'air, votre santé augmente de 3 et votre armure augmente de 2
- Si vous entrez dans de l'eau, votre santé diminue de 5 et votre armure diminue de 10
Si vous entrez dans le feu, votre santé diminue d'ici 20 et votre armure augmente de 5Si votre santé ou votre armure devient <= 0, vous mourrez instantanément
Trouvez le maximum de temps que vous pouvez survivre.
entrée:
La première ligne consiste en un entier T, le nombre de cas de test. Pour chaque cas de test, deux entiers positifs représenteront la santé initiale H et une armure initiale A.
sortie:
Pour chaque cas de test, trouvez le maximum de temps que vous pouvez survivre.
4 Réponses :
Avez-vous essayé dfs? L'état est un tuple de (air | feu | eau, h, a). Ceci a:
3 * 1000 * 1000 = 3,000,000 game states
: Quel devrait être le sommet source et de destination pour ce problème?
La source est les étapes initiales. Le tableau garde une trace du plus grand nombre de mouvements pour atteindre cet état.
En fait, c'est un peu plus compliqué que ce que j'ai laissé, mais l'approche générale devrait fonctionner.
: J'ai déjà beaucoup essayé. La plupart des gens ont semé cette question dans 0.00, alors je pense que cela pourrait être beaucoup plus facile.
Eh bien, il y a une solution analytique. L'ordre que vous visitez les états n'est pas important, configurez donc un système de inégalités linéaires et de les résoudre d'algèbre. (Ou vous pourriez la recherche binaire sur eux.)
@ Andrewtomazos-Fathomling Que voulez-vous dire par ordre dans lequel vous visitez les états n'est pas important? Par exemple, il est facile de trouver un exemple qui vous permet de survivre davantage si vous choisissez d'abord de l'air, car elle augmente la santé et l'armure.
@IVLAD: Non, je veux dire que le coût de la visite de l'air, du feu et de l'eau ne change pas en fonction de l'ordre dans lequel vous le visitez. Il s'agit donc d'une statistique suffisante de simplement demander combien de fois vous visitez chaque état. Voir mon autre réponse.
Voici une autre façon de le faire analytiquement:
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;
Pouvez-vous détailler comment la recherche binaire m ? Dans quel intervalle, et que faites-vous pour une valeur candidate donnée k dans cet intervalle?
Eh bien 0 est toujours correct et 10 ^ 9 est toujours impossible, alors c'est votre intervalle. Pour un m corrigé, vous devez décider si m est OK ou impossible. Manipuler les inégalités en utilisant l'algèbre pour le faire.
À quel point pouvez-vous calculer efficacement vérifier ? Je ne peux pas voir un moyen de le faire beaucoup mieux que la force brute.
Vous avez 6 équations dans 3 inconnues (A, F, W). Rappelez-vous que M, H et A sont maintenant constants. C'est l'algèbre du lycée. (temps constant)
Vous n'avez pas 6 équations, vous avez une équation et au moins 3 inégalités.
C'est ce que je voulais dire. Résolvez le premier pour A ( A = M + F + W ), remplacez-le, laissant 2 inconnus (f, w) - etc.
J'ai fait en utilisant un programme dynamique. DP [Health] [Armure] [Air / Fire / Eau] - Le temps maximum que vous pouvez vivre si vous commencez à partir de cette condition Ensuite, les conditions récurrentes deviennent simplement DP [Santé] [Armure] [Air / Fire / Eau] = 1 + max des états suivants que vous pouvez aller à Il est évident que le cas de base est quand il peut aller nulle part alors la réponse pour cela devient zéro.
D'accord, essayez d'abord de la résoudre par une approche gourmande. Il est évident que l'air est le meilleur choix possible car il augmente à la fois l'armure et la santé, mais vous pouvez aller à l'air alternativement uniquement. Donc, chaque bouge impair (I.E 1,3,5 ...) sera à l'air. Maintenant, nous devons décider quoi faire avec même des mouvements?
Nous avons donc deux choix d'incendie ou d'eau? Nous devons être raisonnables et choisir un tel geste qui maintient à la fois h et a ci-dessus 0. Jumpant maintenant dans les coûts d'incendie Santé -20 Même s'il augmente l'armure de 5, mais hé-wait, quelle est l'utilisation d'une armure accrue si vous n'avez pas ' Tez votre santé> 0. Donc, si H> 5 et A> 10 choisissez de l'eau.
Que si nous sommes à court d'armure mais que nous avons assez de santé? Dans ce cas, nous n'avons pas d'autre choix que de sauter au feu.
Alors, nous avons maintenant une approche gourmande:
Donc, si nous avons suffisamment H et A, nous irons à l'eau. Sinon, si H est suffisant et que A n'est pas suffisant, allez au feu. Sinon, c'est fini!
Voici le lien IDONE de la mise en œuvre:
http://ideone.com/rkobnk
Au cours de l'essentiel, vous n'avez pas besoin de ne pas vérifier le bras <= 10 parce que si H> 20 est vrai, cela signifie si une partie a été fausse parce que le bras était <= 10.
Quelle est l'entrée maximale de H et A?
"Contraintes d'entrée: 1 <= t <= 10 1 <= h, un <= 1000"
Avez-vous essayé la solution gourmande? Allez à l'air chaque fois que possible parce que cela augmente tout, sinon si l'armure> Santé va à l'eau, sinon si cela ne te tue pas, allez au feu.
@IVLAD: Monsieur, j'ai eu une mauvaise réponse avec l'approche que vous avez décrite.can vous prouvez la validité de l'approche gourmande ici
@ user1724072 Non, c'était juste une pensée. Je n'ai pas de gourmande de travail, désolé.