HDOJ 免费馅饼

简单DP，记忆化会RE，递推即可。

# include <cstdio>
# include <cstring>

# define N 100005

int n, t, f[N][11], a[N][11];
int Max(int x, int y){return x>y ? x:y;}
/*int dp(int x, int y)
{
    int &ans = f[x][y];
    if (ans >= 0) return ans;
    if (x > t) return ans = 0;
    ans = 0;
    ans = Max(ans, dp(x+1, y));
    if (y > 0) ans = Max(ans, dp(x+1, y-1));
    if (y < 10) ans = Max(ans , dp(x+1, y+1));
    return ans += a[x][y];
}*/
int main()
{
    int x, y, i, j;
    while (scanf("%d", &n), n)
    {
        t = 0;
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        while (n--)
        {
            scanf("%d%d", &x, &y);
            ++a[y][x];
            if (y > t) t = y;
        }
        for (i = t; i >= 0; --i)
        for (j = 0; j < 11; ++j)
        {
            f[i][j] = f[i+1][j];
            if (j > 0) f[i][j] = Max(f[i+1][j-1], f[i][j]);
            if (j < 10) f[i][j] = Max(f[i+1][j+1], f[i][j]);
            f[i][j] += a[i][j];
        }
        printf("%d\n", f[0][5]);
    }
    
    return 0;
}