hdu 1176 免费馅饼（dp）

免费馅饼

题目链接：

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

解题思路：

数塔的变形。

AC代码：

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

int a[100005][15] ;
int dp[100005][15] ;
int main(){
    int n;
    while(scanf("%d",&n),n){
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        int x, T,maxT = 0;
        while(n--){
            scanf("%d%d",&x,&T);
            ++a[T][x];
            maxT = max(maxT,T);
        }
        dp[1][4] = a[1][4];
        dp[1][5] = a[1][5];
        dp[1][6] = a[1][6];
        for(int i = 2; i <= maxT; ++i){
            for(int j = 0; j <= 10; ++j){
                dp[i][j] = dp[i-1][j];
                if(j > 0)
                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]);
                if(j < 10)
                    dp[i][j] = max(dp[i][j],dp[i-1][j+1]);
                dp[i][j] += a[i][j];
            }
        }
        int ans = 0;
        for(int i = 0; i <= 10; ++i)
            ans = max(ans,dp[maxT][i]);
        printf("%d\n",ans);
    }
    return 0 ;
}