50. 免费馅饼

题目

解析

1. 类似于 30. 三角形最小路径和
2. 不同点：比 30. 三角形最小路径和难，**难于：** 都是一排排的数，而不是三角形，但是思路是一样的，最后看dp[0][6]的值（整体向右挪了一位，并且删除边缘效应，且从上到下，第0秒是最终结果）

代码

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

const int N = 100010;
int dp[N][13];


int main() {
    int n;
    while(~scanf("%d",&n)) {
        if (n == 0) break;
        int maxt = 0;
        memset(dp, 0, sizeof(dp)); // 为什么不加这个会报错????
        for (int i = 0; i < n; i++) {
            int x, t;
            scanf("%d%d", &x, &t);
            dp[t][x + 1]++;
            maxt = max(maxt, t);
        }

        for (int i = maxt - 1; i >= 0; i--) {
            for (int j = 1; j < 12; j++) {
                dp[i][j] += max(dp[i + 1][j - 1], max(dp[i + 1][j], dp[i + 1][j + 1]));
            }
        }

        cout << dp[0][6] << endl;
    }

    return 0;
}