天降猫咪游戏

问题描述

捡猫咪游戏是这样的，猫咪从天上往下掉，且只会掉在 [0, 10] 范围内，具体的坐标范围如下图所示。
初始站在位置五上，且每秒只能在移动不超过一米的范围内接住掉落的猫咪，如果没有接住，猫咪就会跑掉。
例如，在刚开始的一秒内，只能接到四、五、六这三个位置其中一个位置的猫咪。
要求接住尽可能多的猫咪。

Input

多组样例。每组样例输入一个 m (0 < m < 100000)，表示有 m 只猫咪。
在接下来的 m 行中，每行有两个整数 a, b (0 < b < 100000)，表示在第 b 秒的时候有一只猫咪掉落在 a 点上。
注意，同一个点上同一秒可能掉落多只猫咪。m = 0 时输入结束。

Output

输出一个整数 x，表示可能接住的最多的猫咪数。

Sample

Input: 
6
5 1
4 1
6 1
7 2
7 2
8 3
0

Output: 
4

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

用 f[i][j] 表示第 i 秒在 j 位置能接住的猫咪数量，状态转移方程为：

$$f_{i,j}=max(f_{i-1,j-1},f_{i-1,j},f_{i-1,j+1})+a_{i,j}$$

即每秒只能往左、往右或不动，取最大值。

从后往前，可以确定最终位置一定是在 位置 5 上。

源代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 100020;
int arr[maxN][13];

int main() {
	int m;
	while (cin >> m) {
		if (m == 0)
			break;
		for (int i = 0; i <= m + 10; i++)
			for (int j = 0; j < 13; j++)
				arr[i][j] = 0;
		int bPoint = 0;
		while (m--) {
			int a, b;
			cin >> a >> b;
			arr[b][a + 1]++;
			bPoint = max(b, bPoint);
		}
		for (int i = bPoint - 1; i >= 0; i--) {
			for (int j = 1; j <= 11; j++) {
				arr[i][j] += max(arr[i + 1][j + 1], max(arr[i + 1][j], arr[i + 1][j - 1]));
			}
		}
		cout << arr[0][6] << endl;
	}
	return 0;
}