首页 > 代码库 > HDU 1176 免费馅饼
HDU 1176 免费馅饼
这题一开始没想到数塔,嘻嘻;由于是学校DIY里面的题目,所以百度了一下题目,拿到了题目测试数据,用来给freopen用的;
不小心瞄到数塔..不过再想想应该也是可以想到的..分析一下就懂了..
值得一提的是自己被题目骗了..最后一个输入的不一定是最大的时间..耽搁了一会- -找了半天原因嘞;//还有需要记得一点的是:正面不好做可以逆着做,像Super jumping 这类的.
读入数据的时候将每个位置+1,为了统一方法; //把a数组去掉可以将时间从93ms下调至46MS;
下面给出代码:
1 #include<iostream> 2 #define maxn 100010 3 int n,a[13][maxn],dp[13][maxn];//位置,时间 4 using namespace std; 5 int max(int a,int b,int c) 6 { 7 int d=a>b?a:b; 8 return c>d?c:d ; 9 }10 int main()11 {12 //freopen("1176.txt","r",stdin);13 int i,j;14 while(~scanf("%d",&n),n)15 {16 memset(a,0,sizeof(a));17 memset(dp,0,sizeof(dp));18 int i,j,b=0,t,x;19 for(i=1;i<=n;i++)20 {21 scanf("%d%d",&x,&t);22 a[x+1][t]+=1;23 if(b<t) b=t; 24 }25 for(i=0;i<12;i++)26 for(j=0;j<maxn;j++)27 dp[i][j]=a[i][j]; 28 for(i=b-1;i>=0;i--)29 for(j=1;j<12;j++)30 dp[j][i]+=max(dp[j-1][i+1],dp[j][i+1],dp[j+1][i+1]);31 32 printf("%d\n",dp[6][0]);33 34 }35 return 0;36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。