网站链接可以自己做吗,上海火迎网络推广运营优化,软件开发培训学校软件开发培训机构,网站制作多少钱资讯题意#xff1a;
给你一个矩阵#xff0c;问你按照象棋马的走法#xff0c;下一步比上一步的数大#xff0c;问长度最长的序列是多长#xff0c;然后输出序列。如果有多个最长序列输出字典序最小的那个。类似滑雪#xff0c;找出最长路径#xff0c;多个答案 输出字典序…题意
给你一个矩阵问你按照象棋马的走法下一步比上一步的数大问长度最长的序列是多长然后输出序列。如果有多个最长序列输出字典序最小的那个。类似滑雪找出最长路径多个答案 输出字典序最小的。
思路
将矩阵上的数字从大到小排序贪心找路径。。
题目
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). Heres 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 shes 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 cows score; call it W. * Lines 2..W1: 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
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
#define inf 0x3f3f3f3f
const int M400;
int pre[M][M],dp[M][M],w[M][M],m;/*w在该点走到不能再走走了多少步,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默认为从大到小排序优先队列默认为从小到大。{return tt.zz;}
}s[M*M];/*care*/
int main()
{while(~scanf(%d,m)){int k0;for(int i0;im;i)for(int j0;jm;j){scanf(%d,dp[i][j]);s[k].xi;s[k].yj;s[k].zdp[i][j];}sort(s,sk);/*由大到小找便于输出记录的路径最后记录的是起始点的坐标需要注意字典序*/int ans-1,a,b,ccinf;for(int i0;ik;i)/*遍历每一个点作为起始点因为该点以前点都是比该点小大的只能往前走*/{int ma-1,ant,mi;for(int j0;j8;j){int us[i].xe[j][0],vs[i].ye[j][1];if(u0||v0||um||vm)continue;if(maw[u][v]||(maw[u][v]antdp[u][v]))//一方面是控制字典序另一方面走一步越小可能走的步数越多{maw[u][v];antdp[u][v];mij;}}w[s[i].x][s[i].y]ma1;pre[s[i].x][s[i].y]mi;if(ansma1||(ansma1ccdp[s[i].x][s[i].y]))/*控制字典序*/{ccdp[s[i].x][s[i].y];ansma1;as[i].x;bs[i].y;}}printf(%d\n,ans);for(int i1;ians;i){printf(%d\n,dp[a][b]);int kkpre[a][b];ae[kk][0];be[kk][1];}}return 0;
}
