免费馅饼
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18519Accepted Submission(s): 6193
Problem Description
都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:
为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)
Input
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000),表示有n个馅饼掉在这条小径上。在结下来的n行中,每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
Output
每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
这里采用的是自顶向下的。个人觉得采用自底向上会好些,就是说按时间的逆序循环,可以少一些判断。最后输出 arr[0][5]
#include <stdio.h>
#include <string.h>
int n;
int arr[100000][13];
int opts[13], a, b, T;
int mymax(int a, int b, int c) {
a = a > b ? a : b;
return a > c ? a : c;
}
int main() {
while (scanf("%d", &n), n) {
memset(arr, 0, sizeof(arr));
for (int i = 0; i < n; i++) {
scanf("%d %d", &a, &b);
arr[b][a + 1]++;
if (T < b)
T = b;
}
memset(opts, 0, sizeof(opts));
for(int i=1; i<5; i++){ //由于从位置5开始,最开始的几行两端是不可达的
for(int j=0; j<6-i; j++)
arr[i][j] = 0;
for(int j=12; j>6+i; j--)
arr[i][j] = 0;
}
for (int i = 2; i <= T; i++)
for (int j = 1; j <= 11; j++)
arr[i][j] += mymax(arr[i-1][j-1],arr[i-1][j],arr[i-1][j+1]);
int max = 0;
for (int j = 1; j <= 11; j++)
if(max < arr[T][j]) max = arr[T][j];
printf("%d\n",max);
}
return 0;
}
分享到:
相关推荐
HOj DP 分类 HOj DP 分类 HOj DP 分类
hoj小部分题
HOJ题目备份
HOJ题目源码,Java语言描述。Online Judge:http://acm.hit.edu.cn
算法分析课件,以及习题,课件做的不错故分享
湖南大学HOJ部分题目的源代码,包括中国余数定理等内容的讲解
HOJ题目源码,Java语言描述。Online Judge:http://acm.hit.edu.cn
此资源为hoj的离线题库,有了这份资源可以在没有网络情况下刷题喽
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
hoj 部分题目解题报告 c,cpp或java语言描述
GRUB_CMDLINE_LINUX="cgroup_enable=memory swapaccount=1"然后运行以下命令: update-grub && reboot在Node.js项目中安装要求:纱线yarn add hoj-judger自己建造要求:CMake 3.4或更高版本,g ++ 9或更高版本./...
注意数据范围,所以要用long long
acm简单题集,适合初学者交流,400道简单题
c在线题库,希望大家下载 kjbjbk lnknn 你看了可能地方辅导书幅度不断说
基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台OJ (An open source online judge system base on SpringBoot, Springcloud Alibaba and Vue.js !)
杭州电子科技大学ACM-OJ系统的部分代码,对学习数据结构还有算法很有帮助
哈工大hoj1037,详细的源代码,附有注释,可以看懂。
杭州电子科技大学OJ 部分代码。新手必备~~
采用暴力的思想,搜索所有可能路径。 int matrix[7][7]; int n; void inttoseries(int i,int *s) //将数i化为n进制的n位数 {int k,j; for(k=0,j=i;k<n-1;++k) {s[k]=j%n;j/=n;} } int maxcolumn(int *s)//每列...
从零开始重写KOK1 1 BIN 让人物可在地图上使用鼠标跑动