ZOJ Problem Set - 3628
Alice is exploring the wonderland once again and she finds a strange house. In the house, there are n rooms which form a circle so that each room is connected to its two neighbour room. For exmaple, if Alice is in room 2, then she can go into room 1 or room 3, and if she is in room 1, she can go into room 2 or room n.
In each room, there may exists some gold coins which is very valuable for Alice's wonderland trip. Every time when alice move into a room, she can choose to take the gold in the room. However, at the same time, the gold in the 2 neighbour room will disappear. For example, if Alice took the gold in room 2, and there are still gold in room 1 or room 3, then all these gold will disappear.
It costs Alice 1 second to move from one room to another neighbour room. Taking gold doesn't cost any time. Since the house is going to collapse, Alice must leave the house in T seconds. At first Alice is in room S, and she can leave the house from any room.
Please help Alice calculate the maximum gold she can collect in T seconds.
The input contains multiple test cases ( no more than 250 test cases ).
For each case, output one line with an integer which is the maximum gold Alice can collect.
4 1 2 3 4 5 6
In the sample, Alice has just one second, and she was in room 2 at second 0, if she took the 4 gold in room 2, she cannot get any gold in the next second, but if she just move to room 3 at second 1, then she can take the 5 gold and leave the house.
Author: HUANG, Qiao
Contest: ZOJ Monthly, July 2012