Why so serious? --[NKU]schindlerlee

pku2111 Millenium Leapcow

schindlerlee原创,禁止转载和用于商业用途

题目描述:

给定一个矩阵,找一个起始点,由该点开始不断马跳,要求跳到的后一节点比前一节点的值大,问最多可以跳多少步,并且输出跳跃的序列,如果两个跳跃序列步数相同,给出字典序较小的

1 2 4

1 2 3

两个序列当然是后一个较小

 

第一感觉可以求出每个节点的跳跃序列,比较长度得出结果。但是我们发现其中有很多重复的路径,由此想到dp。

 

本来此题如果只要求最长的跳跃步数的话,就是一道比较简单的dp了。但是题目要求输出最小的序列,需要稍微复杂一点的处理。

可以考虑为每个点增加一个pre坐标,指向前一个点,但是这就带来一个问题,要寻找最小的序列,如果有两个相同长度的序列可供当前点选择的话,直接贪心是错误的,下图为反例


可以发现,如果只比较前一点的话,左边的路线是正确的,但是实际上右边的是正确的。注意这一点基本就没问题了。

  1 /* 
  2  * SOUR:pku 2111
  3  * ALGO:dp or search
  4  * DATE: 2009年 08月 29日 星期六 04:16:26 CST
  5  * COMM:
  6  * */
  7 #include<iostream>
  8 #include<cstdio>
  9 #include<cstdlib>
 10 #include<cstring>
 11 #include<algorithm>
 12 using namespace std;
 13 const int maxint = 0x7fffffff;
 14 const long long max64 = 0x7fffffffffffffffll;
 15 #define debug 1
 16 const int N = 410;
 17 int mov[8][2= { {12}, {21}, {-12}, {2-1},    //
 18 {1-2}, {-21}, {-1-2}, {-2-1}
 19 };
 20 
 21 int g[N][N], pre[N][N][2], n, dp[N][N], out[N], on;
 22 struct L {
 23     int x, y;
 24     int val;
 25 } query[N * N];
 26 bool operator <(L a, L b)
 27 {
 28     return a.val < b.val;
 29 }
 30 int a[N*N],b[N*N];
 31 bool judge(int tx,int ty,int px,int py) 
 32 {
 33     int sp = 0,ta,tb,i;
 34     while(tx != -1) {
 35         a[sp] = g[tx][ty];
 36         b[sp] = g[px][py];
 37         sp ++;
 38         ta = pre[tx][ty][0];
 39         tb = pre[tx][ty][1];
 40         tx = ta,ty = tb;
 41 
 42         ta = pre[px][py][0];
 43         tb = pre[px][py][1];
 44         px = ta,py = tb;
 45     }
 46     for(i = sp - 1;i >= 0 && a[i] == b[i];i--);
 47     if(a[i] < b[i])
 48         return true;
 49     return false;
 50 }
 51 
 52 int main()
 53 {
 54     int i, j, k, x, y, big, tx, ty;
 55     scanf("%d"&n);
 56     for (i = 0; i < n; i++) {
 57         for (j = 0; j < n; j++) {
 58             scanf("%d"&g[i][j]);
 59             query[i * n + j].val = g[i][j];
 60             query[i * n + j].x = i;
 61             query[i * n + j].y = j;
 62             pre[i][j][0= pre[i][j][1= -1;
 63         }
 64     }
 65 
 66     sort(query, query + n * n);
 67     for (i = 0; i < n * n; i++) {
 68         x = query[i].x;
 69         y = query[i].y;
 70         for (j = 0; j < 8; j++) {
 71             int tx = x + mov[j][0];
 72             int ty = y + mov[j][1];
 73             if (tx >= 0 && tx < n && ty >= 0 && ty < n
 74                 && g[x][y] > g[tx][ty]) {
 75                 if (dp[x][y] < dp[tx][ty] + 1) {
 76                     dp[x][y] = dp[tx][ty] + 1;
 77                     pre[x][y][0= tx;
 78                     pre[x][y][1= ty;
 79                 } else if (dp[x][y] == dp[tx][ty] + 1) {
 80                     int px = pre[x][y][0];
 81                     int py = pre[x][y][1];
 82                     if (judge(tx,ty,px,py)) {
 83                         pre[x][y][0= tx;
 84                         pre[x][y][1= ty;
 85                     }
 86                 }
 87             }
 88         }
 89     }
 90     on = 0, big = 0;
 91     for (i = 0; i < n; i++) {
 92         for (j = 0; j < n; j++) {
 93             if (dp[i][j] > big) {
 94                 big = dp[i][j];
 95                 x = i, y = j;
 96             }
 97         }
 98     }
 99     while (x != -1 && y != -1) {
100         out[on++= g[x][y];
101         tx = pre[x][y][0];
102         ty = pre[x][y][1];
103         x = tx, y = ty;
104     }
105     printf("%d\n", on);
106     for (i = on - 1; i >= 0; i--) {
107         printf("%d\n"out[i]);
108     }
109     return 0;
110 }
111 

 

posted on 2009-08-29 23:02 schindlerlee 阅读(1196) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理