问题

dp可以解，在每个i 点位置，都有三种选择，1）原地“待饼” 2）左移 3）右移。这里位置可能会重复，所以我们还的加一个状态变量，就是时间，我们用dp[i，j]来表示在第i 秒，在第 j 的位置所得到的最多的馅饼。

则状态转移方程为 ： dp [ i, j ] = max{ dp[ i + 1] [ j ] , dp [ i + 1] [ j - 1] , dp[i + 1] [ j + 1] } ，右边是 i  + 1 ，是因为倒计时。

这还没算完，那我们 最终的状态什么呢，最终会在时间为0 即i = 0，但是 j 是多少呢？ 这鬼知道啊。我们再把问题倒过来看，反正是得到最多的馅饼，那我们就把这个过程中所站的点构成的序列倒过来，前锋断后，后卫变前锋，对，将初始点 j = 5，作为终止的点，那么我们的最终结果就是dp[ 0 ] [ 5 ]了。

#define  _CODE_HDOJ_A1176_
#ifdef _CODE_HDOJ_A1176_
/************************************************************************
f[i][j]: at time i, position j, the max he can get.
trans function: at f[i][j], he has three choices, 1)stand there and go nowhere.
2)go to left. 3)go to right.

f[i][j] = max{f[i+1][j], f[i+1][j+1], f[i+1][j-1]}
/************************************************************************/
#include <stdio.h>
#include <string.h>

const int N = 100002;
const int P = 11;

int f[N][P+2];

inline int max3(int a, int b, int c)
{
	if(a < b) a = b;
	if(a < c) a = c;
	return a;
}

int main()
{
	int n;
	freopen("a1176.txt","r",stdin);
	while (scanf("%d", &n), n)
	{
		int maxtime = -1;
		memset(f, 0, sizeof(f));
		for (int i = 0; i < n; ++i)
		{
			int p, t;
			scanf("%d%d",&p, &t);
			f[t][p+1]++; //0-10 to 1-11
			if(t > maxtime)
				maxtime = t;
		}
		for (int time = maxtime - 1; time >= 0; --time)
		{
			for (int pt = 1; pt <= 11; ++pt)
			{
				f[time][pt] += max3(f[time+1][pt], f[time+1][pt+1],f[time+1][pt-1]);
			}	
		}
		printf("%d\n",f[0][6]);
	}
	return 0;
}
#endif

免费馅饼