首页 > 代码库 > HDU 1176 免费馅饼
HDU 1176 免费馅饼
思路:这道题是数塔模型的一种变形。
首先,我们会看到,随着时间的不同,落下馅饼的位置也会不同,那么我们会考虑到,我们想到第i个点去接馅饼时候,会发现这时我们拥有的馅饼数量是(即状态转移方程):
dp[当前时间][当前位置]+=dp[当前时间-1][上一个位置(仔细思考会发现有3个位置)]
所以AC代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100005; int dp[N][12]; int main() { int n,t,x,maxx,m; while(~scanf("%d",&n)) { if(n==0)break; m=n; maxx=0; memset(dp,0,sizeof(dp)); while(m--) { scanf("%d%d",&x,&t); dp[t][x] ++; if(maxx<t)maxx=t; //优化层次 } for(int i=maxx-1;i >= 0;i --) //从倒数第二层开始向上 { dp[i][0]+=max(dp[i+1][0],dp[i+1][1]); //边界的特殊情况 for(int j=1;j<11;j++) dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]); //3个上一状态的最大值 } printf("%d\n",dp[0][5]); //顶点 } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。