poj1054The Troublesome Frog

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

大部分直接暴力过了

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

注意它必须能跳进和跳出

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define N 5010
 8 bool flag[N][N];
 9 struct node
10 {
11     int x,y;
12 }p[N];
13 bool cmp(node a,node b)
14 {
15     if(a.x==b.x)
16     return a.y<b.y;
17     return a.x<b.x;
18 }
19 int main()
20 {
21     int i,j,k,n,r,c;
22     while(scanf("%d%d",&r,&c)!=EOF)
23     {
24         memset(flag,0,sizeof(flag));
25         scanf("%d",&n);
26         for(i = 1; i <= n ;i++)
27         {
28             scanf("%d%d",&p[i].x,&p[i].y);
29             flag[p[i].x][p[i].y] = 1;
30         }
31         sort(p+1,p+n+1,cmp);
32         int ans=0,ff=1;
33         for(i = 1 ; i <= n ; i++)
34             for(j = i+1; j <= n ; j++)
35             {
36                 int tx = p[j].x-p[i].x;
37                 int ty = p[j].y - p[i].y;
38                 int ox = p[j].x;
39                 int oy = p[j].y;
40                 if(p[i].x-tx>=1&&p[i].x-tx<=r&&p[i].y-ty>=1&&p[i].y-ty<=c)
41                 continue;
42                 ff = 1;
43                 for(k = 2 ; ; k++)
44                 {
45                     ox+=tx;
46                     oy+=ty;
47                     if(ox>r||oy>c||ox<1||oy<1)
48                     break;
49                     if(!flag[ox][oy])
50                     {
51                         ff = 0;
52                         break;
53                     }
54                 }
55                 if(ff)
56                 ans = max(ans,k);
57             }
58         if(ans>2)
59         printf("%d
",ans);
60         else
61         printf("0
");
62     }
63     return 0;
64 }

View Code