poj1054The Troublesome Frog

链接

想O(n*n)的DP  怎么想都超内存 看讨论有说hash+DP过的 实现比较繁琐

大部分直接暴力过了

直接枚举每个i j 与他们在一条线上的点 是不是给出的点

注意它必须能跳进和跳出

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 5010
bool flag[N][N];
struct node
{
int x,y;
}p[N];
bool cmp(node a,node b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int main()
{
int i,j,k,n,r,c;
while(scanf("%d%d",&r,&c)!=EOF)
{
memset(flag,,sizeof(flag));
scanf("%d",&n);
for(i = ; i <= n ;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
flag[p[i].x][p[i].y] = ;
}
sort(p+,p+n+,cmp);
int ans=,ff=;
for(i = ; i <= n ; i++)
for(j = i+; j <= n ; j++)
{
int tx = p[j].x-p[i].x;
int ty = p[j].y - p[i].y;
int ox = p[j].x;
int oy = p[j].y;
if(p[i].x-tx>=&&p[i].x-tx<=r&&p[i].y-ty>=&&p[i].y-ty<=c)
continue;
ff = ;
for(k = ; ; k++)
{
ox+=tx;
oy+=ty;
if(ox>r||oy>c||ox<||oy<)
break;
if(!flag[ox][oy])
{
ff = ;
break;
}
}
if(ff)
ans = max(ans,k);
}
if(ans>)
printf("%d\n",ans);
else
printf("0\n");
}
return ;
}
上一篇:OpenStack Restful API框架介绍


下一篇:[UOJ UR #2]树上GCD