Dima and Magic Guitar CodeForces - 366E
2024-08-25 21:33:08
Dima and Magic Guitar CodeForces - 366E
题意:
http://blog.csdn.net/u011026968/article/details/38716425
http://vawait.com/2013/11/codeforces-366e/
http://www.cnblogs.com/jianglangcaijin/archive/2013/11/25/3441319.html
对于s中任意相邻两个数x和y,都要求在矩形中找出任意两个分别等于x和y的点,然后求其曼哈顿距离,本题要求所有求出的曼哈顿距离的最大值最大。容易想到,应当是让一对点的曼哈顿距离最大,其他点任意即可。也就是对于s中所有相邻两个数,找出矩形中分别等于这两个数且之间曼哈顿距离最大的两个点。
曼哈顿距离等于以下的最大值:
(xa-xb)+(ya-yb)
(xa-xb)-(ya-yb)
-(xa-xb)+(ya+yb)
-(xa-xb)-(ya-yb)
也就是这些的最大值:
(xa+ya)-(xb+yb)
(xa-ya)-(xb-yb)
(-xa+ya)-(-xb+yb)
(-xa-ya)-(-xb-yb)
因此要求值分别为a和b的点间最大的曼哈顿距离,就是这四种的最大值,而每种的最大值都是被减数最大,减数最小。也就是分别记录所有值为a的点中xa+ta,xa-ya,-xa+ya,-xa-ya的最大与最小值。
(这题没有讲不可能完成时怎么处理,也没有这样的数据。)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[];
int max1[][],min1[][];
int n,m,k,s,ans;
int main()
{
int i,j,t;
scanf("%d%d%d%d",&n,&m,&k,&s);
memset(min1,0x3f,sizeof(min1));
memset(max1,,sizeof(max1));
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
scanf("%d",&t);
max1[t][]=max(max1[t][],i+j);
max1[t][]=max(max1[t][],i-j);
max1[t][]=max(max1[t][],-i+j);
max1[t][]=max(max1[t][],-i-j);
min1[t][]=min(min1[t][],i+j);
min1[t][]=min(min1[t][],i-j);
min1[t][]=min(min1[t][],-i+j);
min1[t][]=min(min1[t][],-i-j);
}
scanf("%d",&a[]);
for(i=;i<=s;i++)
{
scanf("%d",&a[i]);
for(j=;j<=;j++)
ans=max(ans,max(max1[a[i-]][j]-min1[a[i]][j],max1[a[i]][j]-min1[a[i-]][j]));
}
printf("%d",ans);
return ;
}
最新文章
- 关于css的一些事情(1)
- 【腾讯Bugly干货分享】iOS黑客技术大揭秘
- js之文档对象的设置(DOM)
- Visual Studio 压力测试注意点
- JQuery安全分析
- Android(java)学习笔记131:Intent启动别的Activity
- 最全ASCLL码
- Android SimpleAdapter ListView (锁定手机,解锁手机的列表)
- ng-click得到当前元素,angular.element()用法
- Cocos2d-x 3.0final手机游戏开发视频教程2014 - 自学编程 -(陆续更新中)
- Oracle cloud control 12c 怎样改动sysmanpassword
- 深入理解javascript new的机制
- 利用smarty模板(登录、有关信息操作等功能)
- Natas Wargame Level 12 Writeup(文件上传漏洞)
- R formulas in Spark and un-nesting data in SparklyR: Nice and handy!
- 2017-5-31 VBA设置config sheet 制作工具
- Ubuntu命令操作
- idea搭建springboot
- BZOJ 3674 可持久化并查集
- Map不同具体实现类的比较和应用场景的分析
热门文章
- 代码书写C++ 中调用传递与指针传递根本区别
- VUE 之 JS指令
- Java中的文件上传和下载
- Android源代码下载过程中无法下载repo的解决方法【转】
- Git 对比两分支中同一文件
- CodeForces546D:Soldier and Number Game(筛区间素数因子个数和)
- BZOJ_2251_[2010Beijing Wc]外星联络_后缀数组
- 【NOIP 2003】 加分二叉树
- C#使用SendMessage发送组合键
- Laravel 5.4 中的异常处理器和HTTP异常处理实例教程