hdu 1176 免费馅饼 变型数塔 dp

分析

题目:题目链接

按题意,t时间会落下一个馅饼在x位置,而处于x’位置的gameboy只能拿到x’+1、x’、x’-1三个位置的馅饼,若将馅饼下落信息用一个数组f[t][x],发现对于每个i,j,gameboy只能取得f[i+1][j+1],f[i+1][j-1],f[i+1][j]三个值,要使得最后取得的值最大,一看这是典型的数塔问题,然后就可以用dp轻松解决了

注意:由于数组每层在计算后不再使用,所以直接用原数组进行滚动,从下往上将结果累加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define MP make_pair
#define mod 1000000007
#define eps 1e-8
#define pi acos(-1.0)
#define inf 0x3fffffff
#define maxn 200055
int f[maxn][20];
int maxx(int a,int b,int c){
return max(max(a,b),c);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
int n;
while(~scanf("%d",&n)&&n){
int t,x;
memset(f,0,sizeof(f));
int mx = 0;
for(int i = 0 ; i < n; i++){
scanf("%d %d",&x,&t);
f[t][x+1] ++;
if(t > mx) mx = t;
}
for(int i = mx -1 ; i > 0; i--){
for(int j = 1; j <= 11;j++){
f[i][j] += maxx(f[i+1][j],f[i+1][j-1],f[i+1][j+1]);
}
}
printf("%d\n",maxx(f[1][5],f[1][6],f[1][7]));
}
}