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

DP(数塔问题) - 免费馅饼 - HDU - 1176

题意：

$有11个位置0,1,2,...,10，初始时站在5号位置，每秒钟可以向任意方向移动一个长度单位，$

$给定n个行数据，每行包括两个整数x和t，表示在t时刻x位置，有一个馅饼，$

$要计算从5出发，最多能够获得多少个馅饼。$

输入：

$多组测试数据，$

$每组包括一个正整数n$

$接着n行，每行两个正整数x和t$

输出：

$一个正整数，表示获得馅饼的最大数量。$

Sample Input

65 14 16 17 27 28 30

Sample Output

4

数据范围：

$0<n,t<100000$

分析：

$如下图：$

$当t>=6时，是事实上可以从5走到0到10的任意位置。$

$如果我们反过来考虑，这就是一个数塔问题。$

$我们记w[i][j]:表示i时刻在j位置处的馅饼数量。f[i][j]:表示t时刻在j位置处最多能够获得的馅饼数量。$

$如果我们自底向上考虑，每个点的最大值都取决于下方连续的2或3个点的最大值。$

$即：f[i][j]=max(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+w[i][j]$

$那么终点就是0时刻在起点位置5的值。$

$考虑到边界问题，为了简化代码，把所有位置向右平移1个长度单位。$

代码：

#include<cstdio>#include<iostream>#include<cstring>#include<vector>#include<queue>using namespace std;const int N=100010;int f[N][15];int n;int w[N][15];int t, x;int main(){       while(~scanf("%d",&n),n)    {           memset(w,0,sizeof w);        memset(f,0,sizeof f);        int T=0;        for(int i=0;i<n;i++)        {               scanf("%d%d",&x,&t);            w[t][x+1]++;            T=max(T,t);        }        for(int i=1;i<=11;i++) f[T][i]=w[T][i];                for(int i=T-1;i>=0;i--)            for(int j=1;j<=11;j++)            {                   f[i][j]=max(f[i+1][j],max(f[i+1][j-1],f[i+1][j+1]))+w[i][j];            }                printf("%d\n",f[0][6]);    }        return 0;}