解题报告:
小明走在一条小路上,这条小路的长度是10米,从左到右依次是0到10一共十个点,现在天上会掉馅饼,给出馅饼掉落的坐标和时间,一开始小明的位置是在坐标为5的位置,
他每秒钟只能移动一米的距离,问他最多能得到多少个馅饼。
这题可以说是一个动态规划题,就是一个数塔的变形,而且跟数塔的区别很小,我们可以把时间当成是数塔中的层,坐标就是数塔中的横向的位置,然后就是从时间最大的那一层出发,往时间最小的方向递归,最后得到的dp[0][5]就是我们所要的结果。
#include<cstdio>
#include<cstring>
#include<iostream>
int max(int a,int b,int c) {
int ans = std::max(a,b);
return std::max(ans,c);
}
int map[][];
int main() {
int n,x,t;
while(scanf("%d",&n)&&n) {
memset(map,,sizeof(map)); //初始化都为0
int Tm = ; //求出最大的时间
for(int i = ;i<=n;++i) {
scanf("%d%d",&x,&t);
Tm = std::max(Tm,t);
map[t][x]++;
}
for(int i = Tm - ;i>=;--i)
for(int j = ;j<=;++j) {
if(j==)
map[i][j] += std::max(map[i+][j],map[i+][j+]);
else if(j==)
map[i][j] += std::max(map[i+][j],map[i+][j-]);
else map[i][j] += max(map[i+][j-],map[i+][j],map[i+][j+]);
}
printf("%d\n",map[][]);
}
return ;
}