NEFU OJ Problem1485 贪吃蛇大作战 题解
2023/11/19 18:32:35
本文主要是介绍NEFU OJ Problem1485 贪吃蛇大作战 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 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<=xi<=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。
需要保证重新排布后性质不变,分析后得知需要满足保持原本的横纵坐标的大小关系即
如下图所示方法,删除所有空行和空列可以实现。
算法实现
- 对\(x\)坐标
由小到大排序
- 对于每个点
遍历
从0开始分配新的\(x'\)坐标,如果某个点\(x\)坐标与上一个点相同
,则分配相同的\(x'\)坐标,而不递增
\(x'\)。
之后再对\(y\)坐标进行同样的操作。
完成后对\(S'\)点集进行DP即可
代码如下
#include <bits/stdc++.h> using namespace std; struct Food { int x, y, v, _x, _y;//_x和_y代表映射后坐标 } food[1020]; int mp[1020][1020], dp[1020][1020]; bool Cmp1(Food f1, Food f2)//x排序 { return f1.x < f2.x; } bool Cmp2(Food f1, Food f2)//y排序 { return f1.y < f2.y; } int Find(int x, int y)//Dp { if(dp[x][y] != -1) return dp[x][y]; int res = 0; if(x-1 >= 0) res = max(res, Find(x-1,y)); if(y-1 >= 0) res = max(res, Find(x,y-1)); return dp[x][y] = res + mp[x][y]; } int main() { int T; cin >> T; while(T--) { int n; cin >> n; for (int i = 0; i < n; i ++) scanf("%d%d%d", &food[i].x, &food[i].y, &food[i].v); //x排序并分配新坐标 sort(food, food+n, Cmp1); int ind_x = 1; food[0]._x = 1; for (int i = 1; i < n; i ++) if(food[i].x == food[i-1].x) food[i]._x = ind_x; else food[i]._x = ++ind_x; //y排序并分配新坐标 sort(food, food+n, Cmp2); int ind_y = 1; food[0]._y = 1; for (int i = 1; i < n; i ++) if(food[i].y == food[i-1].y) food[i]._y = ind_y; else food[i]._y = ++ind_y; //普通DP过程 for (int i = 0; i <= 1000; i ++) for (int j = 0; j <= 1000; j ++) mp[i][j] = 0; for (int i = 0; i < n; i ++) mp[food[i]._x][food[i]._y] = food[i].v; for (int i = 0; i <= ind_x; i ++) for (int j = 0; j <= ind_y; j ++) dp[i][j] = -1; dp[0][0] = 0; cout << Find(ind_x,ind_y) << endl; } return 0; }
这篇关于NEFU OJ Problem1485 贪吃蛇大作战 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-27数据结构与算法面试题详解及练习
- 2024-12-27网络请求面试题详解与实战
- 2024-12-27数据结构和算法面试真题详解与实战教程
- 2024-12-27网络请求面试真题解析与实战教程
- 2024-12-27数据结构和算法大厂面试真题详解与实战指南
- 2024-12-27TS大厂面试真题解析与应对策略
- 2024-12-27TS大厂面试真题详解与解析
- 2024-12-27网站安全入门:如何识别和修复漏洞
- 2024-12-27SQL注入基础教程
- 2024-12-27初学者指南:理解和修复跨域漏洞