HDU1176：免费馅饼（dp,数字三角形的应用）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1176

这题就是数字三角行的变形，可惜对于我这个渣渣来说就是没发现，区别是他可以保持在三个点，他左边的点，右边的点，还有原点，

从下往上处理。其他就没有什么好说的了，注意一下细节问题，我记得这题我白白贡献了几次WA.

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

#define inf 0x3f3f3f3f

typedef long long ll;

using namespace std;

int n,dp[][],h[][];

int main()

{

    int xx,yy,zan;

    while(scanf("%d",&n)!=EOF&&n!=)

    {

        zan=-;

        for(int i=; i<; i++)

        {

            for(int j=; j<; j++)

            {

                dp[i][j]=;

                h[i][j]=;

            }

        }

        for(int i=; i<n; i++)

        {

            scanf("%d%d",&xx,&yy);

            zan=max(zan,yy);

            h[xx][yy]++;

        }

        if(zan<=)

        {

            for(int i=zan; i>=; i--)

            {

                for(int j=-i; j<=+i; j++)

                {

                    dp[j][i]=max(dp[j][i],dp[j][i+]+h[j][i]);

                    dp[j][i]=max(dp[j][i],dp[j-][i+]+h[j][i]);

                    dp[j][i]=max(dp[j][i],dp[j+][i+]+h[j][i]);

                }

            }

            int sum=max(dp[][],dp[][]);

            sum=max(dp[][],sum);

            printf("%d\n",sum);

            continue;

        }

        for(int i=zan; i>=; i--)

        {

            for(int j=; j<=; j++)

            {

                dp[j][i]=max(dp[j][i],dp[j][i+]+h[j][i]);

                if(j>=)

                    dp[j][i]=max(dp[j][i],dp[j-][i+]+h[j][i]);

                if(j<=)

                    dp[j][i]=max(dp[j][i],dp[j+][i+]+h[j][i]);

            }

        }

        for(int i=; i>=; i--)

        {

            for(int j=-i; j<=+i; j++)

            {

                dp[j][i]=max(dp[j][i],dp[j][i+]+h[j][i]);

                dp[j][i]=max(dp[j][i],dp[j-][i+]+h[j][i]);

                dp[j][i]=max(dp[j][i],dp[j+][i+]+h[j][i]);

            }

        }

        int sum=max(dp[][],dp[][]);

        sum=max(dp[][],sum);

        printf("%d\n",sum);

    }

    return ;

}