博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVa 10285 - Longest Run on a Snowboard
阅读量:6627 次
发布时间:2019-06-25

本文共 2142 字,大约阅读时间需要 7 分钟。

称号:给你一个二维矩阵,找到一个点。每一个可以移动到的位置相邻的上下,求最长单调路径。

分析:贪婪,dp。搜索。

这个问题是一个小样本,我们该怎么办。

            这里使用贪心算法:

            首先。将全部点依照权值排序(每一个点一定被值更大的点更新);

            然后,按顺序更新排序后。每一个点更新周围的点;

            最后,找到最大值输出就可以。

说明:╮(╯▽╰)╭居然拍了1000+,还以为这样的方法比較快呢(数据分布啊╮(╯▽╰)╭)。

#include 
#include
#include
#include
using namespace std;typedef struct nodep{ int value,x,y;}point;point now,Node[10004];char buf[256];int maps[102][102];int imap[102][102];int dmap[102][102];int cmp1( point a, point b ){ return a.value > b.value;}int cmp2( point a, point b ){ return a.value < b.value;}int main(){ int T,R,C,dxy[4][2] = {1,0,0,1,-1,0,0,-1}; while ( ~scanf("%d",&T) ) while ( T -- ) { scanf("%s%d%d",buf,&R,&C); int count = 0; for ( int i = 1 ; i <= R ; ++ i ) for ( int j = 1 ; j <= C ; ++ j ) { scanf("%d",&maps[i][j]); imap[i][j] = dmap[i][j] = 1; Node[count].value = maps[i][j]; Node[count].x = i; Node[count].y = j; count ++; } sort( Node, Node+count, cmp1 ); for ( int i = 0 ; i < count ; ++ i ) { for ( int j = 0 ; j < 4 ; ++ j ) { now.x = Node[i].x+dxy[j][0]; now.y = Node[i].y+dxy[j][1]; if ( now.x >= 1 && now.x <= R && now.y >= 1 && now.y <= C ) { if ( maps[now.x][now.y] < maps[Node[i].x][Node[i].y] ) if ( dmap[now.x][now.y] < dmap[Node[i].x][Node[i].y]+1 ) dmap[now.x][now.y] = dmap[Node[i].x][Node[i].y]+1; } } } sort( Node, Node+count, cmp1 ); for ( int i = 0 ; i < count ; ++ i ) { for ( int j = 0 ; j < 4 ; ++ j ) { now.x = Node[i].x+dxy[j][0]; now.y = Node[i].y+dxy[j][1]; if ( now.x >= 1 && now.x <= R && now.y >= 1 && now.y <= C ) { if ( maps[now.x][now.y] > maps[Node[i].x][Node[i].y] ) if ( imap[now.x][now.y] < imap[Node[i].x][Node[i].y]+1 ) imap[now.x][now.y] = imap[Node[i].x][Node[i].y]+1; } } } int max = 0; for ( int i = 1 ; i <= R ; ++ i ) for ( int j = 1 ; j <= C ; ++ j ) { if ( max < imap[i][j] ) max = imap[i][j]; if ( max < dmap[i][j] ) max = dmap[i][j]; } printf("%s: %d\n",buf,max); } return 0;}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4646440.html,如需转载请自行联系原作者

你可能感兴趣的文章
理解SQL代理错误日志
查看>>
维护计划作业
查看>>
Multipart Internet Mail Extensions (MIME)
查看>>
C# WinForm控件之Dock顺序调整
查看>>
中控科技 ZK Software的售后服务真像一坨屎,技术人员嚣张
查看>>
NSPredicate过滤数组数据
查看>>
设置MYSQL允许用IP访问
查看>>
spark 数据预处理 特征标准化 归一化模块
查看>>
大道至简,系统设计和模块划分的实用经验之谈
查看>>
正则表达式中参数g、i、m的作用(share)
查看>>
使用Solr构建企业级的全文检索(四)---------写入文档
查看>>
squid的正向代理和反向代理
查看>>
linux下命令与文件的查询
查看>>
SEO意识的网站设计:设计和SEO的完美结合可能么?
查看>>
IP 算法
查看>>
IBM_System_x3650服务器固件升级手顺
查看>>
awk单行脚本
查看>>
软件开发之通病解析
查看>>
python wxPython 5 (框架 wx.Frame)
查看>>
windows server backup 功能备份虚拟机
查看>>