Week13 作业 C

题目描述：

思路：

• 符合最优子结构

• 定义状态：f[i][j]表示在第i秒结束时，位置在j处能接到的总量的最大值

• 状态转移：f[i][j]= max(f[i - 1][j - 1], max(f[i-1][j], f[i-1][j+1])) + d[i][j]，即位置j可以从j-1，j，j+1三个位置转移过来

• 边界条件：f[0][j]=0，第0秒包里一定是空的

• 答案：max{f[T][j]}，T表示最后的时间

• 这样对吗？？？不对，因为f[T][j]不知道是由谁转移过来的，进一步也就没法确定f[T][j]的起始状态是不是在5号点，所以信息不足，难道要增加维度吗？

• 其实，可以逆序搜索，相当于把时间倒放，f[0][5]是最后的状态，这样就能符合题目要求了，状态转移和边界条件上述稍微一修改即可，思想不变

总结：

题目限制了状态的转移，则就要考虑当前状态是不是合法的

代码：

因为为了使用第一次定义的状态转移，为了防止数组下标为负，把坐标统统加了1（全部向右移动一个单位），不过因为发现逆序才更好，所以没啥用，但是懒得改了

//设f[i][j]表示在第i秒结束时,位置在j处能接到的猫的最大值
//	f[i][j]= max(f[i - 1][j - 1], max(f[i-1][j], f[i-1][j+1])) + d[i][j];
//因为用到i-1,所以把整个坐标轴向右平移1个单位
//初始化f[0][j]=0;
//问题:必须从位置5开始,但是最后的位置是不确定的,可以逆着来
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
int f[MAXN][15], d[MAXN][15];
int main()
{
	int M;
	while (scanf("%d", &M) && M != 0)
	{
		memset(f, 0, sizeof(f));
		memset(d, 0, sizeof(d));
		int maxT = 0;
		for (int i = 1; i <= M; i++)
		{
			int t, x;
			scanf("%d %d", &x, &t);
			d[t][x + 1]++;
			maxT = max(t, maxT);
		}
		for (int i = maxT; i >= 0; i--)
		{
			for (int j = 1; j <= 11; j++)
			{
				f[i][j] = max(f[i + 1][j - 1], max(f[i + 1][j], f[i + 1][j + 1])) + d[i][j];
			}
		}
		cout << f[0][6] << endl;
	}
	return 0;
}