首页 > 代码库 > HDU 1176 免费馅饼
HDU 1176 免费馅饼
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1176
解题思路:
本题是简单的数塔dp。
可以参考博客:
http://blog.csdn.net/theonegis/article/details/45801201
实现代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=100010; const int INF=1<<20; int data[MAXN][14]; int dp[MAXN][14]; int main(){ int n; while(scanf("%d",&n)!=EOF&&n){ memset(data,0,sizeof(data)); memset(dp,0,sizeof(dp)); int MAXT=-INF; for(int i=0;i<n;i++){ int x,T; scanf("%d%d",&x,&T); data[T][x+1]++; //注这儿的x都加了1 MAXT=max(MAXT,T); } for(int i=MAXT;i>=0;i--){ for(int j=1;j<=11;j++) dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]))+data[i][j]; } printf("%d\n",dp[0][6]); } }
HDU 1176 免费馅饼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。