題意：

給你一個(gè)矩陣，問你按照象棋馬的走法，下一步比上一步的數(shù)大，問長度最長的序列是多長，然后輸出序列。如果有多個(gè)最長序列輸出字典序最小的那個(gè)。類似滑雪，找出最長路徑，多個(gè)答案 輸出字典序最小的。

思路：

將矩陣上的數(shù)字從大到小排序，貪心找路徑。。

題目：

The cows have revised their game of leapcow. They now play in the middle of a huge pasture upon which they have marked a grid that bears a remarkable resemblance to a chessboard of N rows and N columns (3 <= N <= 365).?

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

* Line 1: A single integer: the size of the board

* 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

* Line 1: A single integer that is the winning cow's score; call it W.?

* 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 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f const int M=400; int pre[M][M],dp[M][M],w[M][M],m;/*w在該點(diǎn)走到不能再走，走了多少步,pre記錄路徑*/ int e[8][2]={2,1,1,2,-1,-2,-2,-1,1,-2,-1,2,2,-1,-2,1};/*記憶化+暴力+care字典序*/ struct node {int x,y,z;bool operator<(const node &tt)const//sort默認(rèn)為從大到小排序，優(yōu)先隊(duì)列默認(rèn)為從小到大。{return tt.z<z;} }s[M*M];/*care*/ int main() {while(~scanf("%d",&m)){int k=0;for(int i=0;i<m;i++)for(int j=0;j<m;j++){scanf("%d",&dp[i][j]);s[k].x=i;s[k].y=j;s[k++].z=dp[i][j];}sort(s,s+k);/*由大到小找，便于輸出記錄的路徑，最后記錄的是起始點(diǎn)的坐標(biāo)，需要注意字典序*/int ans=-1,a,b,cc=inf;for(int i=0;i<k;i++)/*遍歷每一個(gè)點(diǎn)，作為起始點(diǎn)，因?yàn)樵擖c(diǎn)以前點(diǎn)都是比該點(diǎn)小大的，只能往前走*/{int ma=-1,ant,mi;for(int j=0;j<8;j++){int u=s[i].x+e[j][0],v=s[i].y+e[j][1];if(u<0||v<0||u>=m||v>=m)continue;if(ma<w[u][v]||(ma==w[u][v]&&ant>dp[u][v]))//一方面是控制字典序，另一方面走一步越小，可能走的步數(shù)越多{ma=w[u][v];ant=dp[u][v];mi=j;}}w[s[i].x][s[i].y]=ma+1;pre[s[i].x][s[i].y]=mi;if(ans<ma+1||(ans==ma+1&&cc>dp[s[i].x][s[i].y]))/*控制字典序*/{cc=dp[s[i].x][s[i].y];ans=ma+1;a=s[i].x;b=s[i].y;}}printf("%d\n",ans);for(int i=1;i<=ans;i++){printf("%d\n",dp[a][b]);int kk=pre[a][b];a+=e[kk][0];b+=e[kk][1];}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Millenium Leapcow POJ - 2111 （千禧年跳牛）（贪心找最长路径，记忆化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。