首页 > 代码库 > HDU 1176 免费馅饼
HDU 1176 免费馅饼
裸DP,刚开始没想到转化为数字三角形的模型。墨迹了好久。
不过这个题的数据规模真让人蛋疼,T=0是存在的.....
#include<stdio.h> #include<string.h> int max (int a, int b, int c) { if (b > a) { a = b; } if (c > a) { a = c; } return a; } int i,j; int a[100010][15]; int main() { int n; while(scanf("%d",&n)!=EOF,n) { memset(a,0,sizeof(a)); int x,t; int last=0; while(n--) { scanf("%d%d",&x,&t); a[t][x+1]++; // 将数组整体右移 省略边界考虑 if(t>last) { last=t; } } for(i=last;i>=0;i--) { for(j=1;j<=11;j++) { a[i][j]+=max(a[i+1][j],a[i+1][j+1],a[i+1][j-1]); } } printf("%d\n",a[0][6]); } return 0; }
HDU 1176 免费馅饼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。