Description
In Korea, the naughtiness of the cheonggaeguri, a small frog, is legendary. This is a well-deserved reputation, because the frogs jump through your rice paddy at night, flattening rice plants. In the morning, after noting which plants have been flattened, you want to identify the path of the frog which did the most damage. A frog always jumps through the paddy in a straight line, with every hop the same length:
Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure-1, and the troublesome frogs hop completely through your paddy, starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure-2:
Many frogs can jump through the paddy, hopping from rice plant to rice plant. Every hop lands on a plant and flattens it, as in Figure-3. Note that some plants may be landed on by more than one frog during the night. Of course, you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy ?for the situation in Figure-3, what you can see is shown in Figure-4:
From Figure-4, you can reconstruct all the possible paths which the frogs may have followed across your paddy. You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy. Such a path is said to be a frog path. In this case, that means that the three paths shown in Figure-3 are frog paths (there are also other possible frog paths). The vertical path down column 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested; and the diagonal path including the plants on row 2 col. 3, row 3 col. 4, and row 6 col. 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants, and hence it is not a frog path. Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path (see the plant at (2, 6) on the horizontal path across row 2 in Figure-4), and in fact some flattened plants may not be explained by any frog path at all.
Your task is to write a program to determine the maximum number of landings in any single frog path (where the maximum is taken over all possible frog paths). In Figure-4 the answer is 7, obtained from the frog path across row 6.
Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure-1, and the troublesome frogs hop completely through your paddy, starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure-2:
Many frogs can jump through the paddy, hopping from rice plant to rice plant. Every hop lands on a plant and flattens it, as in Figure-3. Note that some plants may be landed on by more than one frog during the night. Of course, you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy ?for the situation in Figure-3, what you can see is shown in Figure-4:
From Figure-4, you can reconstruct all the possible paths which the frogs may have followed across your paddy. You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy. Such a path is said to be a frog path. In this case, that means that the three paths shown in Figure-3 are frog paths (there are also other possible frog paths). The vertical path down column 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested; and the diagonal path including the plants on row 2 col. 3, row 3 col. 4, and row 6 col. 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants, and hence it is not a frog path. Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path (see the plant at (2, 6) on the horizontal path across row 2 in Figure-4), and in fact some flattened plants may not be explained by any frog path at all.
Your task is to write a program to determine the maximum number of landings in any single frog path (where the maximum is taken over all possible frog paths). In Figure-4 the answer is 7, obtained from the frog path across row 6.
十分蛋疼的题意描述，就是给一个图，上面有很多点，然后问最长的一个轨迹是多少。
刚开始想错了方向，一直在想从整体的角度怎么DP，后来百度发现是搜索，然后才想到了直接枚举两个点，然后dfs就好，其中加上记忆化，就可以了。
注意卡内存，所以说要hash存点，hash值也要取个合适的，第一次就TLE了。。。
代码如下：
// ━━━━━━神兽出没━━━━━━ // ┏┓ ┏┓ // ┏┛┻━━━━━━━┛┻┓ // ┃ ┃ // ┃ ━ ┃ // ████━████ ┃ // ┃ ┃ // ┃ ┻ ┃ // ┃ ┃ // ┗━┓ ┏━┛ // ┃ ┃ // ┃ ┃ // ┃ ┗━━━┓ // ┃ ┣┓ // ┃ ┏┛ // ┗┓┓┏━━━━━┳┓┏┛ // ┃┫┫ ┃┫┫ // ┗┻┛ ┗┻┛ // // ━━━━━━感觉萌萌哒━━━━━━ // Author : WhyWhy // Created Time : 2015年07月20日 星期一 08时55分13秒 // File Name : 1054.cpp #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MaxN=5005; int R,C; short dp[MaxN][MaxN]; int N; struct Point { int x,y; bool operator < (const Point &b) const { if(x==b.x) return y<b.y; return x<b.x; } }P[MaxN]; inline bool in(int x,int y) { return x<=R && x>=1 && y<=C && y>=1; } const int HASH=1000003; struct HASHMAP { int head[HASH],next[MaxN],Hcou; unsigned long long key[MaxN]; int rem[MaxN]; void init() { Hcou=0; memset(head,-1,sizeof(head)); } void insert(unsigned long long val,int id) { int h=val%HASH; for(int i=head[h];i!=-1;i=next[i]) if(val==key[i]) return; rem[Hcou]=id; key[Hcou]=val; next[Hcou]=head[h]; head[h]=Hcou++; } int find(unsigned long long val) { int h=val % HASH; for(int i=head[h];i!=-1;i=next[i]) if(val==key[i]) return rem[i]; return 0; } }map1; int dfs(int u,int v) { if(dp[u][v]) return dp[u][v]; int dx=(P[v].x<<1)-P[u].x,dy=(P[v].y<<1)-P[u].y; if(!in(dx,dy)) return 2; int rP=map1.find(dx*10000+dy); if(!rP) { dp[u][v]=-1; return -1; } dp[u][v]=dfs(v,rP)+1; return dp[u][v]; } inline bool judge(int u,int v) { int dx=(P[u].x<<1)-P[v].x,dy=(P[u].y<<1)-P[v].y; return !in(dx,dy); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int ans=-100; scanf("%d %d",&R,&C); scanf("%d",&N); for(int i=1;i<=N;++i) scanf("%d %d",&P[i].x,&P[i].y); sort(P+1,P+N+1); map1.init(); for(int i=1;i<=N;++i) map1.insert(10000*P[i].x+P[i].y,i); for(int i=1;i<=N;++i) for(int j=i+1;j<=N;++j) if(judge(i,j)) ans=max(ans,dfs(i,j)); if(ans<3) ans=0; printf("%d ",ans); return 0; }