Topcoder_155

【问题描述】

    Tom是一只懒猫，它想捉住在附近的老鼠，但是它不想离开它最喜爱待的椅子。幸运的是，它可以使用抛帽子来捉住老鼠，凡是在它d米附近的所有老鼠它都能够准确的通过帽子捉住，但是没抛一次它需要休息一会儿，并且每顶帽子也只能使用一次。

    开始的时候（time=0），第i只老鼠所在的位置距离Tom pos[i]米，并且它跑的速度是每秒speed[i]米，因此k秒后，它距离Tom将是pos[i] + k * speed[i]米。给定Tom n顶帽子（0～n-1），它可以按照任意的顺序抛帽子，每抛一次要休息rest[i]秒。现在对于给定的有效距离d，需要计算出Tom最多能捉住多少只老鼠。

  定义：

类  LazyCat

方法  public int maxMiceCount(int[] pos, int[] speed, int d, int[] rest)

  约束：

1、pos、speed、rest均包含1至50个元素，并且元素个数一样，取值在1至1000；

2、有效距离d为0至1000。

  测试用例：

1、{4, 1, 2} {1, 1, 1} 3 {3, 2, 1}   Returns: 2

2、{5, 5, 5} {1, 1, 1} 5 {1, 1, 1}   Returns: 1

3、{13, 5, 8} {10, 10, 10} 15 {1, 1, 1}   Returns: 2

1. public class LazyCat {
2.     public int maxMiceCount(int[] pos, int[] speed, int d, int[] rest) {
3.         int[] newPos = new int[pos.length];
4.         int count = 0, max = 0;
5.         for (int i = 0; i < pos.length; i++) {
6.             if (pos[i] > d)
7.                 continue;
8.             for (int k = 0; k < pos.length; k++) {
9.                 newPos[k] = pos[k] + speed[k] * rest[i];
10.             }
11.             // 使得这个帽子不能再被使用（因为此处的老鼠已经被捉，不可能被捉2次）
12.             newPos[i] = d + 1;
13.             count = 1 + maxMiceCount(newPos, speed, d, rest);
14.             if (count > max)
15.                 max = count;
16.         }
17.         return max;
18.     }
19. }