pppz
BAN USEROh, it doesn't mention if the player has to meet the enemies in the given order or the player can decide the order of the enemies which makes the problem totally different. I assumed the player can decide the order. If the player can decide the order, then just bride enemies until the player's strength reaches to the strongest enemy's strength then fight rest of them.
If the player cannot decide the order, then DP will reduce the complexity.
Additionally, it doesn't need to reduce player's strength when it fights.
ChrisZ, I cannot leave comment on your post. But I see some problem on your solution
It doesn't say that the player keep the enemy's money when fight. It just says "keep Your money" which doesn't mean player keep the enemy's money but it means the player's money doesn't reduced when fight.
And your algorithm doesn't consider of the facing order(which enemy the player meet first.) The right solution is finding enemies to bride to get enough power to beat the strongest enemy then fight rest of all. It doesn't need DP. Just sort enemies by strength order then check combination which makes the sum of power is greater than (the strongest enemy's power - player's initial power)
ChrisZ, I cannot leave comment on your post. But I see some problem on your solution
It doesn't say that the player keep the enemy's money when fight. It just says "keep Your money" which doesn't mean player keep the enemy's money but it means the player's money doesn't reduced when fight.
And your algorithm doesn't consider of the facing order(which enemy the player meet first.) The right solution is finding enemies to bride to get enough power to beat the strongest enemy then fight rest of all. It doesn't need DP. Just sort enemies by strength order then check combination which makes the sum of power is greater than (the strongest enemy's power - player's initial power)
What does MoveToFront actually do? Does it move the given number and all other number shift by one, which takes O(n) times? or just swap the first number and the given number?
It's confusing since it's array and we usually don't do move front then push all others back by one.
@DyingLizard, it looks like your solution assume
- pppz February 19, 2018010
110
000
is a 3x3 square. Did I misunderstand your code?