动态规划：捡猫游戏

题面：

捡猫咪游戏规则如下：
猫咪从天上往下掉，且只会掉在 [0, 10] 范围内，具体的坐标范围如下图所示

TT 初始站在位置五上，且每秒只能在移动不超过一米的范围内接住掉落的猫咪，如果没有接住，猫咪就会跑掉。例如，在刚开始的一秒内，TT 只能接到四、五、六这三个位置其中一个位置的猫咪。
请求出最多可能接到的猫咪数

多组样例输入。每组样例输入一个 m (0 < m < 100000)，表示有 m 只猫咪。
在接下来的 m 行中，每行有两个整数 a b (0 < b < 100000)，表示在第 b 秒的时候有一只猫咪掉落在 a 点上。
注意，同一个点上同一秒可能掉落多只猫咪。m = 0 时输入结束

输出一个整数 x，表示 TT 可能接住的最多的猫咪数

sample input：
6
5 1
4 1
6 1
7 2
7 2
8 3
0

sample output:
4

思路：

• 对于第一秒，4,5,6位置没有区别，可以直接将值付到dp数组中。
• 对于之后的转移过程需要分情况，对于边界的两个点（0，10位置），只存在单边界的转移，而对于中间位置可以从三个状态进行转移
• 根据分析可以列出状态转移方程，对于题目给出的最大时间 li ,
• 出现MLE不要怕，微笑着面对他 ，看一下自己数组是不是开大了，尤其是像我们要使用memset对数组进行初始化的情况；如果还不行，就看一下是否存储了不必要的大数，比如代码中的const int N.本来我定义数组用了N，换成直接定义后就成功AC了。

#include
#include
#include
#include
using namespace std;
//const int N=1e6+1;
int a[100001][11],dp[100001][11];
int thmax(int a,int b,int c)
{int temp=max(a,b);temp=max(temp,c);return temp;
}
int main()
{int m;while(scanf("%d",&m)!=EOF){if(m==0) return 0;int pos,tim;memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));int li=0;for(int i=1;i<=m;i++){scanf("%d%d",&pos,&tim);a[tim][pos]++;li=max(li,tim);}dp[1][4]=a[1][4];dp[1][5]=a[1][5];dp[1][6]=a[1][6];for(int i=2;i<=li;i++){for(int j=0;j<=10;j++){if(j==0)//单独边界处理dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j];else if(j==10)dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];else dp[i][j]=thmax(dp[i-1][j+1],dp[i-1][j],dp[i-1][j-1])+a[i][j];}}int ans=0;for(int i=0;i<=10;i++)ans=max(ans,dp[li][i]);printf("%d\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！