首页 > 代码库 > UVA10599 - Robots(II)(变形的LIS)
UVA10599 - Robots(II)(变形的LIS)
题意:一个机器人在n * m的网格里面捡垃圾,机器人只能向右或向下走,求出能捡到的垃圾数量的最大值,有多少条路径可以达到最大值,以及输出其中一条路径。
思路:按照题意可以看出,因为机器人只能向右和向下走,所以纵坐标就不重要的,而横坐标是递增的。当将所有拥有垃圾的格子经过计算得到它的一维值(唯一的),得到一组的数组。那就可以转化为求最长上升子序列。但这个LIS的条件是mod(m)要大于前一个。计算数量时,当d[i] = d[j] + 1时,就相当于以i为结束时的最长上升子序列比以j结束时的最长上升子序列大1,那么达到d[i]的路径的数量就为v[i] += v[j];同理当d[i] < d[j] + 1时,v[i] = v[j];至于路径的输出就使用记录数组,递归输出。
自己在初始化将图转化为数组WA了,后来看了别人的改了过来,但还是不懂为什么那样子不对。。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10005; int g[105][105], d[MAXN], arr[MAXN], v[MAXN], path[MAXN]; int n, m, cnt; void init () { memset(g, 0, sizeof(g)); int a, b; cnt = 0; while (scanf("%d %d", &a, &b) && a && b) { g[a][b] = 1; //arr[cnt++] = (a - 1) * m + b - 1; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j]) arr[cnt++] = (i - 1) * m + j - 1; if (!g[n][m]) arr[cnt++] = n * m - 1; } void LIS() { memset(path, -1, sizeof(path)); memset(v, 0, sizeof(v)); memset(d, 0, sizeof(d)); for (int i = 0; i < cnt; i++) { d[i] = 1, v[i] = 1; for (int j = 0; j < i; j++) if (arr[i] % m >= arr[j] % m) { if (d[i] < d[j] + 1) { d[i] = d[j] + 1; path[i] = j; v[i] = v[j]; } else if (d[i] == d[j] + 1) v[i] += v[j]; } } if (!g[n][m]) d[cnt - 1]--; } void outPut(int u) { if (path[u] != -1) outPut(path[u]); if (u != cnt - 1 || g[n][m]) printf(" %d", arr[u] + 1); } int main() { int t = 1; while (scanf("%d %d", &n, &m) != EOF) { if (n == -1 && m == -1) break; init(); LIS(); printf("CASE#%d: %d %d", t++, d[cnt - 1], v[cnt - 1]); outPut(cnt - 1); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。