Catching the Thief
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
In the Qingshui Village, there's a clever thief and a cleverer police.
There are N houses in Qingshui Village which are located in a straight line. And the N houses are numbered from 1 to N according to the direction of the line. Two houses are consided to be neighbor of each other if and only if there is no other house between them.
The thief hides in one of N houses now, and the police tries to find him out. Every day the police will choose a house to check and he will catch the thief if he hides in that house. If the thief survive the arrest of the police, in the night he will move to a neighboring house to pass through the next day.
What is the number of days the police needs to catch the thief in the worst case?
Remember that the police is a clever man.
Input
In the first line, an integer T (T <= 100) indicates the number of cases.
T lines follow. Each contains an integer N described above. (1 <= N <= 10000)
Output
For each test case, output “Case x: d” in which x is the number of test case counted from one, and d is the number of days before the police catch the thief in the worst case.
Sample Input
2 1 2
Sample Output
Case 1: 1 Case 2: 2
Hint
Case 1: There is only one room, so the police can catch the thief on the first day. Case 2: There are two rooms. The police can check room 1 on the first day. The worst case is that the thief is in room 2, but in this case the police can check room 1 on the second day and will catch the thief for sure.
這道題目首先要解出前面四個的解
房間為一個的時候答案為1天
房間為兩個的時候答案為2天
房間為三個的時候答案為2天
房間為四個的時候答案為4天
第五個房子則能夠遞推。例如以下圖
從左往右走。一步步排除。小偷所在的房子。dp[2]代表着兩個房間裡最多用多少天能夠抓住小偷，如此，我們能夠不斷遞推，先排除，左邊兩個房間會出現小偷的情況，接着右邊還有三個房子，可是為什麼圖中将第二個房子都給畫圈了。由于我們排除了最左邊的房子不會出現小偷，可是此時無法防止第二個房子不會再出現小偷。如此要将他算進去，是以dp[5] = dp[2] + dp[4]如此不斷遞推得出終于的狀态轉移方程
dp[n] = dp[2] + dp[n - 1]
