免费馅饼 （变形的数塔）

本题思路对了就很好写
数塔的变形

从第5秒之后可能走的位置就在0到10内
仔细分析 和以前做的题目的区别与联系

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100005][15];
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        memset(dp,0,sizeof(dp));
        int t=-0x3f3f3f3f;
        for(int i=1; i<=n; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(b>t)
                t=b;
            dp[b][a]++;
        }

        for(int i=t-1; i>=0; i--)
        {
            if(i>=5)
            {
                for(int j=0; j<=10; j++)
                {
                    if(j==0)
                        dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
                    else dp[i][j]+=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
                }
            }
            else for(int j=5-i;j<=5+i;j++)
            {
                dp[i][j]+=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
            }
        }
        printf("%d
",dp[0][5]);
    }
    return 0;
}