题目链接

看到分类里是dp,结果想了半天,也没想出来,搜了一下题解,全是暴力!

不过剪枝很重要,下面我的代码 266ms。

题意:

在一个矩阵方格里面,青蛙在里面跳,但是青蛙每一步都是等长的跳,

从一个边界外,跳到了另一边的边界外,每跳一次对那个点进行标记。

现在给你很多青蛙跳过后的所标记的所有点,那请你从这些点里面找出

一条可能的路径里面出现过的标记点最多。

分析:先排序(目的是方便剪枝,break),然后枚举两个点,这两个

点代表这条路径的起始的两个点。然后是三个剪枝,下面有。

开始遍历时,预判当前能否产生比ans更好地解,若不能,直接跳到下一个。。。。

注意标记点必须>=3,否则输出0.

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Max(a,b)((a)>(b)?(a):(b))
using namespace std;
const int maxn = + ;
bool f[maxn][maxn];
int n, r, c, cx, cy;
struct node
{
int x, y;
}p[maxn]; bool cmp(node a, node b)
{
if(a.y == b.y)
return a.x < b.x;
else
return a.y < b.y;
}
bool check(int x, int y)
{
if(x>=&&x<=r && y>=&&y<=c)
return true;
return false;
}
int cal(int px, int py)
{
int sum = ;
while()
{
if(!check(px+cx, py+cy))
break;
if(f[px+cx][py+cy])
{
sum++;
px += cx; py += cy;
}
else
return ;
}
return sum;
}
int main()
{
int i, j, ans;
while(~scanf("%d%d", &r, &c))
{
memset(f, , sizeof(f));
scanf("%d", &n);
for(i = ; i < n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
f[p[i].x][p[i].y] = true;
}
sort(p, p+n, cmp); ans = ;
for(i = ; i < n; i++)
for(j = i+; j < n; j++)
{
cx = p[j].x - p[i].x; cy = p[j].y - p[i].y;
if(check(p[i].x-cx, p[i].y-cy)) //判断是不是从稻田之外跳过来的
continue;
if(p[i].y+ans*cy>c) //因为y是递增的,如果最大的ans 在稻田之外,后面也都大于
break;
if(!check(p[i].x+ans*cx, p[i].y+ans*cy))
continue; //这个不要写成break,因为x不是递增的,有可能前一个出界,但是后一个不出界。
ans = Max(ans, cal(p[i].x, p[i].y));
}
if(ans < )
printf("0\n");
else
printf("%d\n", ans);
}
return ;
}

最新文章

  1. 转评:你造promise就是monad吗
  2. Mac OS X Terminal 101:终端使用初级教程
  3. 完成端口(CompletionPort)详解
  4. python学习笔记13(模块、包)
  5. LINUX下使用crontab进行RMAN备份实验
  6. Hadoop 2.2.0 HA构造
  7. 浅谈JavaScript中typeof与instanceof的区别
  8. windows 7 &amp; protobuf 3.0 &amp; python 3.5
  9. 使用windows上 mxnet 预编译版本
  10. MFC画笔作用域的问题
  11. Java常用类--数字常用类
  12. sed命令(二)
  13. Python随笔--对象
  14. 【COCI 2015/2016 #3】Nekameleoni
  15. 100Mbps和100Mb/s有什么不同
  16. 怎样利用ADO中的adoquery进行缓存更新?????(100分)
  17. ionic2 隐藏滚动条
  18. vsftpd安装配置以及常见问题解决
  19. kotlin 插件更新到 1.2.41 程序出错 Please use kotlin-stdlib-jdk7 instead
  20. JavaScript笔记 #07# 用js写算法

热门文章

  1. 【原创】书本翻页效果booklet jquery插件系列之简介
  2. C++中使用心得
  3. java 把URL中的中文转换成utf-8编码
  4. 移动端页面使用rem来做适配
  5. 《剑指Offer》- 面试题3
  6. UI框架说明
  7. 【转载】错误 CS0016: 未能写入输出文件“c:/WINDOWS/Microsoft.NET/Framework/v2.0.50727/Temporary ASP.NET Files/.........dll”--“拒绝访问。 ”
  8. texCUBE() to CubemapSampler.Sample()
  9. LVS+Keepalived实现高可用集群
  10. winform Chart控件 获取鼠标处坐标值方法