本文主要是介绍hdu1176免费馅饼(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1176
这道题一开始我也是没思路。。结果发现是数塔问题
把它看作一个矩阵，i 表示时间 j 表示地点。
AC代码：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=180000;
int map[maxn][12],dp[maxn][12];
int main()
{int n,x,t,maxt=0,l,r,m,ans=0;while(~scanf("%d",&n) && n){memset(map,0,sizeof(map));memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d%d",&x,&t);map[t][x+1]++;if(t>maxt)maxt=t;}for(int i=1;i<=11;i++)dp[maxt][i]=map[maxt][i];for(int i=maxt-1;i>=0;i--){for(int j=1;j<=11;j++){l=dp[i+1][j+1]+map[i][j];r=dp[i+1][j-1]+map[i][j];m=dp[i+1][j]+map[i][j];dp[i][j]=max(l,r);dp[i][j]=max(dp[i][j],m);}}printf("%d\n",max(dp[0][5],dp[0][6]));}
}
这篇关于hdu1176免费馅饼(DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
