看到分类里是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 ;
}