# HDU-1176 简单的DP
## [HDU-1176](http://acm.hdu.edu.cn/showproblem.php?pid=1176)
## 分析
一个非常朴素的DP题. 主要难点在于发现时间从后往前逆推时最优解的无后效性(**一旦当前时刻的下一个时刻情况确定, 那么当前时刻的情况也唯一确定**), 从前往后则没有这样的特性.
**对每一个时刻$i$中的每一点$j$, 都有:**
- 若$j$不为边界, 则$i$时刻的$j$位置可以获得的最大总收益为以下项之和:
- $i$时刻$j$位置本身掉下的馅饼数
- $(i+1)$时刻的$(j-1,j,j+1)$三个位置掉下的馅饼数的最大值
- 若$j$处于边界(0|10), 则最大总收益中不考虑$(j-1)$和$(j+1)$即可
容易想到DP的经典操作: **补零**. **给时刻和位置的计量值都+1**, 即可空出一个0位. 这样之后, $j$的边界变为(1|11), 初始位置为6, 初始时刻为1. 将0位保持为0, 即可简化讨论情况, 不影响结果.
经过简单整理, 即可得出状态转移方程 ($dp[i][j]$中需要先存放输入数据)
## 转移方程
$$
\begin{aligned}
初始值: &dp[i][j]=\begin{cases}
0, && i越界 \lor j越界 \\
掉落馅饼数, && 其它 \\
\end{cases} \\
递推值: &dp[i][j]=dp[i][j] + max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])
\end{aligned}
$$
## 代码
```cpp
// -------------- GLOBAL ----------------
int dp[100050][15];
// -------------- FUNC ----------------
// -------------- MAIN ----------------
int main() {
//ios_base::sync_with_stdio(false);
int n;
while (~scanf("%d", &n) && n != 0) {
fill0(dp);
int maxt = -INF;
F1(i, n) {
int x, t;
scanf("%d%d", &x, &t);
++dp[++t][++x];
maxt = max(maxt, t);
}
F1R(i, maxt) {
F1(j, 11) {
dp[i][j] += max(max(dp[i + 1][j - 1], dp[i + 1][j + 1]), dp[i + 1][j]);
}
}
printf("%d\n", dp[1][6]);
}
return 0;
}
```
![]()