本文共 1458 字，大约阅读时间需要 4 分钟。

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 
   
    #include 
    
     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
    
   

转载地址：http://urlji.baihongyu.com/