关键词：
Description
Here‘s how they set up the board for the new leapcow game:
* First, the cows obtain N x N squares of paper. They write the integers from 1 through N x N, one number on each piece of paper.
* Second, the ‘number cow‘ places the papers on the N x N squares in an order of her choosing.
Each of the remaining cows then tries to maximize her score in the game.
* First, she chooses a starting square and notes its number.
* Then, she makes a ‘knight‘ move (like the knight on a chess board) to a square with a higher number. If she‘s particularly strong, she leaps to the that square; otherwise she walks.
* She continues to make ‘knight‘ moves to higher numbered squares until no more moves are possible.
Each square visited by the ‘knight‘ earns the competitor a single point. The cow with the most points wins the game.
Help the cows figure out the best possible way to play the game.
Input
* Lines 2.. ...: These lines contain space-separated integers that tell the contents of the chessboard. The first set of lines (starting at the second line of the input file) represents the first row on the chessboard; the next set of lines represents the next row, and so on. To keep the input lines of reasonable length, when N > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.
Output
* Lines 2..W+1: Output, one per line, the integers that are the starting square, the next square the winning cow visits, and so on through the last square. If a winning cow can choose more than one path, show the path that would be the ‘smallest‘ if the paths were sorted by comparing their respective ‘square numbers‘.
Sample Input
4 1 3 2 16 4 10 6 7 8 11 5 12 9 13 14 15
Sample Output
7 2 4 5 9 10 12 13
题意：给你一个矩阵，问你按照象棋马的走法，下一步比上一步的数大，问长度最长的序列是多长，然后输出序列。如果有多个最长序列输出字典序最小的那个。
这是看到的一个代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 #include <algorithm> 7 #include <map> 8 using namespace std; 9 typedef pair<int,int>P; 10 const double eps=1e-9; 11 const int maxn=200100; 12 const int mod=1e9+7; 13 const int INF=1e9; 14 int M[370][370],dp[370][370]; 15 int N; 16 int dx[8]= {1,1,2,2,-1,-1,-2,-2}; 17 int dy[8]= {2,-2,1,-1,2,-2,1,-1}; 18 P path[370][370]; 19 vector<P>res; 20 int DP(int x,int y) 21 { 22 int &m=dp[x][y]; 23 if(m) return m; 24 m=1; 25 for(int i=0; i<8; i++) 26 { 27 int nx=x+dx[i]; 28 int ny=y+dy[i]; 29 if(1<=nx&&nx<=N&&1<=ny&&ny<=N&&M[nx][ny]>M[x][y]) 30 { 31 if(m<DP(nx,ny)+1) 32 { 33 m=DP(nx,ny)+1; 34 path[x][y]=make_pair(nx,ny); 35 } 36 else if(DP(nx,ny)+1==m) 37 { 38 if(M[path[x][y].first][path[x][y].second]>M[nx][ny]) 39 { 40 path[x][y]=make_pair(nx,ny); 41 } 42 } 43 } 44 } 45 return m; 46 } 47 int main() 48 { 49 while(~scanf("%d",&N)) 50 { 51 for(int i=1; i<=N; i++) 52 { 53 for(int j=1; j<=N; j++) 54 { 55 scanf("%d",&M[i][j]); 56 } 57 } 58 int MAX=1,cnt; 59 for(int i=1; i<=N; i++) 60 { 61 for(int j=1; j<=N; j++) 62 { 63 cnt=DP(i,j); 64 if(MAX<cnt) 65 { 66 MAX=cnt; 67 res.clear(); 68 res.push_back(make_pair(i,j)); 69 } 70 else if(MAX==cnt) 71 { 72 res.push_back(make_pair(i,j)); 73 } 74 } 75 } 76 int keyx,keyy,key; 77 key=INF; 78 for(int i=0; i<res.size(); i++) 79 if(M[res[i].first][res[i].second]<key) 80 { 81 key=M[res[i].first][res[i].second]; 82 keyx=res[i].first; 83 keyy=res[i].second; 84 } 85 printf("%d ",MAX); 86 while(1) 87 { 88 printf("%d ",M[keyx][keyy]); 89 int t=path[keyx][keyy].second; 90 keyx=path[keyx][keyy].first; 91 keyy=t; 92 if(!keyx) 93 break; 94 } 95 } 96 return 0; 97 }
知识点：
这个代码的主要想法是，如同最短路一样，path中储存的是当前节点的下一步应该走的位置，然后进行搜索直到遍历了所有的点。
poj3635优先队列+打标记+广搜
AftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvariedbetweenthecitiesyouvisited.Maybeyoucouldhavesavedsomemoneyifyouwereabitmorecleveraboutwhereyoufilled 查看详情
uva167（八皇后）poj2258——记两个简单回溯搜索(代码片段)
UVa167题意：八行八列的棋盘每行每列都要有一个皇后，每个对角线上最多放一个皇后，让你放八个，使摆放位置上的数字加起来最大。参考：https://blog.csdn.net/xiaoxiede_wo/article/details/799731711#include<iostream>2#include<cstring>3#incl... 查看详情
poj3537crossesanscrosses
poj.org/problem?id=3537 (题目链接)题意：给出一个1*n的棋盘，每次可以选择一个没被标记过的点打标记，若经过某一步操作使得出现3个连续的标记，则最后操作的人获胜。问是否存在先手必胜策略。Solution 我们可以很快... 查看详情
java-poj1013-counterfeitdollar
...枚硬币中找出fake的那一个输入：三次天平称量结果1packagepoj.ProblemSet;23importjava.util.Scanner;45/*6我怎么觉得是贪心算法呢？7起初对所有硬币标记0；8如果是even，则两边所有的硬币记为真(记233)；9否则就对不确定的硬币记录怀疑(++或... 查看详情
poj1015
#include<iostream>#include<cmath>#include<algorithm>#include<cstring>usingnamespacestd;intn;//候选总人数intm;//当选人数intdp[21][801];//dp[i][j],选出i个人,这i个人的辩方和控方值的差为jintnum[21][801];//记 查看详情
poj2411mondriaan'sdream(状压dp)
题意：给出一个n*m的棋盘，及一个小的矩形1*2，问用这个小的矩形将这个大的棋盘覆盖有多少种方法。析：对第（i，j）位置，要么不放，要么竖着放，要么横着放，如果竖着放，我们记第（i，j）位置为0，（i+1，j）为1，如果... 查看详情
poj1830开关问题
记\(a_i,j\)表示第\(j\)个开关对第\(i\)号开关产生的影响，\(x_i\)为对第\(i\)个开关的操作，则\[\begincasesa_1,1x_1\\mathrmxor\a_1,2x_2\\mathrmxor\\cdots\\mathrmxor\a_1,nx_n=start_1\\mathrmxor\end_1\a_2,1x_1\\mathr 查看详情
[poj1416]shreddingcompany（dfs）
题目链接：http://poj.org/problem?id=1416题意：一段数分成好几段相加，求最大的且不大于目标值的组合。DFS，用vector<int>tmp来记录中间结果，回溯的时候pop掉。判重用了个map，其实用一个flag打标记也可。1#include<algorithm>2#inclu... 查看详情
动规-poj-3186
http://poj.org/problem?id=3186TreatsfortheCows给定一个双端队列dq，其中有n个正整数元素。每次可从dq头或者尾中取出1个元素。第i次（从1开始计数）取出的元素能带来的权值为i*元素值。问能取得的最大权值。解题报告思路假设现在的状... 查看详情
poj3977：subset——题解（三分+折半搜索）
http://poj.org/problem?id=3977题目大意：有一堆数，取出一些数，记他们和的绝对值为w，取的个数为n，求在w最小的情况下，n最小，并输出w，n。————————————————&md 查看详情
poj2420，模拟退火算法，费马点
题目链接：http://poj.org/problem?id=2420题意：给n个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。 参考链接：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html这一篇文章写的很好，我这个小白都有一... 查看详情
poj2443setoperation题解(代码片段)
http://poj.org/problem?id=2443http://bailian.openjudge.cn/practice/2443?lang=en_US题意：给定一堆集合和一堆询问，每次询问给出两个数(x,y)，如果(x)和(y)出现在了同一个集合内，则输出Yes，否则输出No。考虑把每个数字所出现的位置记下来，并使... 查看详情
poj3714raid（平面最近点对）
题意： 给定在同一平面中，同数量黑点与白点的坐标值，求其中最近黑白点对的距离。————————————————————————————————————————————————————————————... 查看详情
poj-1475pushingboxes
这题我是1A的(其实在POJ上交了无数次)做的时候一开始还读错题了,冷静调样例时才发现要Push数最少时Walk最少具体思路:BFS啦,只是状态好像要记很多多东西啦,什么人的位置,箱子的位置啦,推了几次啊,走了几步啊用个优先队列好像... 查看详情
poj2480longge'sproblem
欲求\(\sum_i=1^n(i,n)\)。显然\((i,n)\midn\)。记\(d=(i,n)\)，枚举\(d\)，有多少个\(i\in[1,n]\)使得\((i,n)=d\)呢？换句话说有多少个\(i\in[1,\lfloorn/d\rfloor]\)使得\((i,\lfloorn/d\rfloor)=1\)呢？显然是\(\varphi(\lfloorn/d\rfloor)\)个。答案就 查看详情
[poj1741]tree
题意：给一棵带边权的树，统计距离$\leqk$的点对数量这个这么基础的东西居然鸽了那么久，我还是退役吧...点分治用于统计满足某些性质的点对或路径，但实际上就是个大暴力这题要求统计树上距离$\leqk$的点对数量，那么我们... 查看详情
poj1186方程的解数
与其说这题是双向广搜板子不如说是哈希表板子...就像邻接表一样，哈希表挂的链就是邻接表的边把计数器记在边权上偷懒一开始看错了条件。。。记得先模再加mod再模，防止负数GG有一个显然的事情是，模数大了空间会大，模... 查看详情
poj1135dominoeffect（spfa）
题目大概是，普通骨牌连接两张关键骨牌，一旦一张关键骨牌倒下与其相邻的普通骨牌也倒下，普通骨牌倒下与其相邻的骨牌也倒下。给出所有有普通骨牌相连的两个关键骨牌之间普通骨牌倒下所需时间，问1号关键骨牌开始倒... 查看详情