POJ 1054 The Troublesome Frog 枚举

这个题分类是dp，想了一会没有想出来，就去看别人题解了。发现别人题解全是暴力枚举= =。复杂度超过 N^2，但可能是剪枝的作用，没有超时。

思路：将所有点按坐标由小到大排序。两两枚举点p1,p2，并判断其中坐标较小的点p1是否是该路径上青蛙跳至的第一个点（假设在p1之前还有一点，则可以根据p1和p2的距离算出p1前一点的坐标，判断该坐标是否在麦田内，若不在则说明p1是青蛙跳至的第一个点）。判定p1前一点坐标时，我原以为由于所有点的坐标都是排好序的（从小到大），则p1前一点的坐标必然更小，因此判定它是否在麦田内时只需要判断是否坐标都大于0，并不需要判断是否超坐标上限。但这种思路是错误的。见下图。

上图情况中，排好序后两两枚举，则到点2与点3时，p1是点2，p2是点1，则p1的前一点在图中的虚线上，此时明显需要判断该点是否超过麦田的坐标上限。

通过上述判断规则，如果p1不是青蛙跳至的第一个点，则跳过该次枚举（因为它必然包含在某次枚举的情况里）。如果是，则根据p1到p2的坐标变化，判断p2后面所有要跳至的点是否都存在。如果存在，则该次枚举是有效的。记录该路径跳的次数。

最后求所有次数的最大值即可。

下面是代码：

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 #include<algorithm>

 #define maxn 5005

 using namespace std;

 struct nod

 {

     int x, y;

     bool operator < (const nod &cmp) const

     {

         if (x == cmp.x) return y < cmp.y;

         return x < cmp.x;

     }

 }rice[maxn];

 bool map[maxn][maxn];

 int main()

 {

     int r, c, n;

     //freopen("data.in", "r", stdin);

     scanf("%d%d%d",&r,&c,&n);

     memset(map, , sizeof(map));

     for (int i = ; i < n; i++)

     {

         scanf("%d%d",&rice[i].x, &rice[i].y);

         map[rice[i].x][rice[i].y] = ;

     }

     sort(rice, rice + n);

     int res = ;

     for (int i = ; i < n; i++)

         for (int j = i + ; j < n; j++) if (i != j)

         {

             int dx = rice[j].x - rice[i].x;

             int dy = rice[j].y - rice[i].y;

             if (rice[i].x - dx >=  && rice[i].x - dx <= r && rice[i].y - dy >=  && rice[i].y - dy <= c) continue;

             int nx = rice[j].x + dx;

             int ny = rice[j].y + dy;

             int len = ;

             int ok = ;

             while (nx >  && nx <= r && ny >  && ny <= c && ok)

             {

                 if (map[nx][ny]) len++;

                 else ok = ;

                 nx += dx;

                 ny += dy;

             }

             if (ok && len > ) res = max(res, len);

         }

     printf("%d", res);

     return ;

 }