题目描述:
在大家不辞辛劳的帮助下,TT 顺利地完成了所有的神秘任务。
神秘人很高兴,决定给 TT 一个奖励,即白日做梦之捡猫咪游戏。
捡猫咪游戏是这样的,猫咪从天上往下掉,且只会掉在 [0, 10] 范围内,具体的坐标范围如下图所示。
TT 初始站在位置五上,且每秒只能在移动不超过一米的范围内接住掉落的猫咪,如果没有接住,猫咪就会跑掉。例如,在刚开始的一秒内,TT 只能接到四、五、六这三个位置其中一个位置的猫咪。
喜爱猫咪的 TT 想要接住尽可能多的猫咪,你能帮帮他吗?
Input
多组样例。每组样例输入一个 m (0 < m < 100000),表示有 m 只猫咪。
在接下来的 m 行中,每行有两个整数 a b (0 < b < 100000),表示在第 b 秒的时候有一只猫咪掉落在 a 点上。
注意,同一个点上同一秒可能掉落多只猫咪。m = 0 时输入结束。
Output
输出一个整数 x,表示 TT 可能接住的最多的猫咪数。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
题目分析:
这个题目的数据就比较正常了,这里用的是动态规划的方法。我们需要用一个数组dp[i][j]来表示第i秒第j点所有的最大猫咪数目。
int dp[100001][11];
初始的时候我们要把有猫咪的地方个数++,然后要找到哪一个时间是最大的,我们从最大时间往前找到0秒,然后找每一个位置可能的情况。
int mn=-114514;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
dp[b][a]++;
mn=max(mn,b);
}
对于每一个情况而言,能捕捉到左右和中间三个格子的猫咪,那么这里获得的猫咪数的最大值就是包括原点的周围三个点的猫咪数目的最大值,多个数的最大值就是max函数的嵌套,毕竟max有交换律和结合律,不管是谁先谁后都一样。
dp[i][j]=dp[i][j]+max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
对于边上两个点,那就是他和附近一个点共两个点的情况了,这要单独的列出来。
dp[i][0]=dp[i][0]+max(dp[i+1][0], dp[i+1][1]);
dp[i][10]=dp[i][10]+max(dp[i+1][10],dp[i+1][9]);
最终的结果就是第0秒(我们的时间是倒着数的)第5个位置(就是原始位置)。
cout<<dp[0][5]<<endl;
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
int dp[100001][11];
int main()
{
int m;
while(cin>>m)
{
if(m==0)
{
break;
}
memset(dp,0,sizeof(dp));
int mn=-114514;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
dp[b][a]++;
mn=max(mn,b);
}
for(int i=mn-1;i>=0;i--)
{
for(int j=1;j<=9;j++)
{
dp[i][j]=dp[i][j]+max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
}
dp[i][0]=dp[i][0]+max(dp[i+1][0], dp[i+1][1]);
dp[i][10]=dp[i][10]+max(dp[i+1][10],dp[i+1][9]);
}
cout<<dp[0][5]<<endl;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)