# 杰拉斯的博客

## [ACM_HDU_1176]免费馅饼（二维动态规划）

### 免费馅饼

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12017 Accepted Submission(s): 3997

```6
5 1
4 1
6 1
7 2
7 2
8 3
0
```

```4
```

#### Source

HDU1176

1. f[i - 1][j - 1]
2. f[i - 1][j]
3. f[i - 1][j + 1]

`f[i][j] = max(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + a[i][j];`

```#include<iostream>
#include<algorithm>
using namespace std;
int a[12][100002];
int f[12][100002];
int main(){
int n;
while(scanf("%d", &n) != EOF && n){
memset(a, 0, sizeof(a));
memset(f, 0, sizeof(f));
int x, T, i, j, maxT = 0, ans = 0;
while(n--){
scanf("%d%d", &x, &T);
++a[x][T];
maxT = max(maxT, T);
}
for(i = 0; i < 11; ++i){
for(j = 1; j <= maxT; ++j){
if(j == 1 && (i < 4 || i > 6)){
continue;
}
f[i][j] = f[i][j - 1];
f[i][j] = max(f[i][j], f[i - 1][j - 1]);
f[i][j] = max(f[i][j], f[i + 1][j - 1]);
f[i][j] += a[i][j];
}
}
for(i = 0; i < 11; ++i)
ans = max(ans, f[i][maxT]);
printf("%d\n", ans);
}
return 0;
}
```

```#include<iostream>
#include<algorithm>
using namespace std;
int a[100001][12];
int f[100001][12];
int main(){
int n;
while(scanf("%d", &n) != EOF && n){
memset(a, 0, sizeof(a));
memset(f, 0, sizeof(f));
int x, T, i, j, maxT = 0, ans = 0;
while(n--){
scanf("%d%d", &x, &T);
++a[T][x];
maxT = max(maxT, T);
}
f[1][4] = a[1][4];
f[1][5] = a[1][5];
f[1][6] = a[1][6];
for(i = 2; i <= maxT; ++i){
for(j = 0; j < 11; ++j){
f[i][j] = f[i - 1][j];
if(j > 0)
f[i][j] = max(f[i][j], f[i - 1][j - 1]);
if(j < 10)
f[i][j] = max(f[i][j], f[i - 1][j + 1]);
f[i][j] += a[i][j];
//printf("%d ", f[i][j]);
}
//printf("\n");
}
for(i = 0; i < 11; ++i)
ans = max(ans, f[maxT][i]);
printf("%d\n", ans);
}
return 0;
}
```

#### 5 条评论 »

1. Kevis

这题错了吧，兄弟，你没考虑在5位置出发能不能到最大的点的情况吧? 比如 第二秒 0位置有5个馅饼，但是这五个馅饼是在第二秒得不到的啊

1. 是不是没看完？第二个答案是能 Accept 的。

1. 0.0

你可以试试3 0 2 0 2 0 2这样的数据

如果是从底部向上加就行了

2. [...]http://www.clanfei.com/2012/04/646.html[...]

3. [...]http://www.clanfei.com/2012/04/646.html[...]