经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
NEFU OJ Problem1485 贪吃蛇大作战 题解
来源:cnblogs  作者:eChorgi  时间:2023/11/20 8:56:55  对本文有异议

题目连接Problem - 1496 (nefu.edu.cn)

  • Problem:F
  • Time Limit:1000ms
  • Memory Limit:65535K

题目

Description

贪吃蛇大家一定都玩过吧,现在宋哥也要玩这个游戏,最初的时候贪吃蛇从屏幕的左下角出发,但是有一个非常不幸的事情,就是宋哥的游戏机的左键和下键坏掉了,这意味着什么?没错!他只能操控他的蛇向右或向上走了,假设屏幕被划分为109*109的格子,而贪吃蛇从坐标为(1,1)的格子出发,每次操作可以从坐标为(x,y)的格子前往坐标为(x+1,y)或(x,y+1)的格子,在所有格子中有一些格子中有一些食物,宋哥现在想知道,他的贪吃蛇最多能吃到多少食物呢?

Input

输入的第一行包含一个数字T(1<=T<=10),代表数据组数,之后的每组数据的每一行包含一个数字n (1<=n<=1000),代表有食物的格子数量,之后的n行每一行包含三个数字xi(1<=xi<=109),yi(1&lt;=xi&lt;=109),pi(1<=xi<=10^6),分别代表格子的坐标和在这个格子里的食物数量。

Output

输出T行,第i行为第i组数据的答案。

Sample Input

2
3
1 1 1
2 2 2
3 3 3
3
1 3 1
2 2 2
3 1 3

Sample Output

6
3

Hint

Source

MGH

思路

看起来像很经典的dp问题,但是区别是点很稀疏,只有1e3的点,却有1e9*1e9的棋盘,考虑将点位置重新紧密排布, 建立一个映射将稀疏点集\(S\)映射到紧密点集\(P'\)\(f:\{P_i = (X_i,Y_i)\in S\}\rightarrow \{P'_i=(X'_i,Y'_i)\in S'\}\)使得\(S'\)方便使用dp。

需要保证重新排布后性质不变,分析后得知需要满足保持原本的横纵坐标的大小关系即

\[\forall P_i, P_j\in S \left\{ \begin{array}{c} x_i < x_j \rightarrow x'_i < x'_j\ x_i = x_j \rightarrow x'_i = x'_j\ x_i > x_j \rightarrow x'_i > x'_j\\end{array} \right. \]

\[\forall P_i, P_j\in S \left\{ \begin{array}{c} y_i < y_j \rightarrow y'_i < y'_j\ y_i = y_j \rightarrow y'_i = y'_j\ y_i > y_j \rightarrow y'_i > y'_j\\end{array} \right. \]

如下图所示方法,删除所有空行和空列可以实现。

image-20231119131303148 image-20231119131531135 image-20231119131346987

算法实现

  1. \(x\)坐标由小到大排序
  2. 对于每个点遍历从0开始分配新的\(x'\)坐标,如果某个点\(x\)坐标与上一个点相同,则分配相同的\(x'\)坐标,而不递增\(x'\)

之后再对\(y\)坐标进行同样的操作。

完成后对\(S'\)点集进行DP即可

代码如下

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct Food
  4. {
  5. int x, y, v, _x, _y;//_x和_y代表映射后坐标
  6. } food[1020];
  7. int mp[1020][1020], dp[1020][1020];
  8. bool Cmp1(Food f1, Food f2)//x排序
  9. {
  10. return f1.x < f2.x;
  11. }
  12. bool Cmp2(Food f1, Food f2)//y排序
  13. {
  14. return f1.y < f2.y;
  15. }
  16. int Find(int x, int y)//Dp
  17. {
  18. if(dp[x][y] != -1)
  19. return dp[x][y];
  20. int res = 0;
  21. if(x-1 >= 0)
  22. res = max(res, Find(x-1,y));
  23. if(y-1 >= 0)
  24. res = max(res, Find(x,y-1));
  25. return dp[x][y] = res + mp[x][y];
  26. }
  27. int main()
  28. {
  29. int T;
  30. cin >> T;
  31. while(T--)
  32. {
  33. int n;
  34. cin >> n;
  35. for (int i = 0; i < n; i ++)
  36. scanf("%d%d%d", &food[i].x, &food[i].y, &food[i].v);
  37. //x排序并分配新坐标
  38. sort(food, food+n, Cmp1);
  39. int ind_x = 1;
  40. food[0]._x = 1;
  41. for (int i = 1; i < n; i ++)
  42. if(food[i].x == food[i-1].x)
  43. food[i]._x = ind_x;
  44. else
  45. food[i]._x = ++ind_x;
  46. //y排序并分配新坐标
  47. sort(food, food+n, Cmp2);
  48. int ind_y = 1;
  49. food[0]._y = 1;
  50. for (int i = 1; i < n; i ++)
  51. if(food[i].y == food[i-1].y)
  52. food[i]._y = ind_y;
  53. else
  54. food[i]._y = ++ind_y;
  55. //普通DP过程
  56. for (int i = 0; i <= 1000; i ++)
  57. for (int j = 0; j <= 1000; j ++)
  58. mp[i][j] = 0;
  59. for (int i = 0; i < n; i ++)
  60. mp[food[i]._x][food[i]._y] = food[i].v;
  61. for (int i = 0; i <= ind_x; i ++)
  62. for (int j = 0; j <= ind_y; j ++)
  63. dp[i][j] = -1;
  64. dp[0][0] = 0;
  65. cout << Find(ind_x,ind_y) << endl;
  66. }
  67. return 0;
  68. }

原文链接:https://www.cnblogs.com/eChorgi/p/17841939.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号