当前位置: 首页 > news >正文

luogu P1648 看守

题目大意

给定 \(d\) 维坐标的 \(n\) 个点,每个点表示为 \(d\) 个数值,求两点间最大距离
\(d\) 维两点间距离为 \(|x_1-y_1|+|x_2-y_2|+...+|x_d-y_d|\)

Sol

我们随便找两个点 \(A\)\(B\) 作为演示:

\[dis_{A,B}=|x_1-y_1|+|x_2-y_2|+...+|x_d-y_d| \]

\(q\)\(1\)\(-1\),其实还可以写成:

\[dis_{A,B}=(qx_1-qy_1)+...+(qx_d-qy_d) \]

(其中 \(q\) 不是同一个值)

如果这就是最大距离的话,我们改动任意一个 \(q\) 都会导致结果不优于当前结果
所以我们可以表示成:

\[\max_{q\in{-1,1}} \{(qx_1-qy_1)+...+(qx_d-qy_d)\} \]

可以给每个 \(q\) 单独赋值, 所得结果最大值即为最大距离

所以令 \(0\) 表示 \(1\) , \(1\) 表示 \(-1\) 压缩到一个 \(d\) 位二进制数中(跟状压dp很像)
我们只需要扫一遍 \([0,2^d-1]\) 就能找到答案
注意: 其中存在无用状态, 但一定会被最终结果覆盖

Code

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>using namespace std;const int N = 1e6+10;
const int INF = 0x3f3f3f3f;int n , m;
vector<int> vec[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n >> m;for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j <= m ; j ++) {int x; cin >> x;vec[i].push_back(x);}int res = 0;for(int state = 0 ; state < (1<<m)-1 ; state ++) {int minx = INF , maxx = -INF;for(int i = 1 ; i <= n ; i ++) {int v = 0;for(int j = 0 ; j < m ; j ++)if(state & (1 << j)) v += vec[i][j];else v -= vec[i][j];minx = min(minx , v);maxx = max(maxx , v);}res = max(res , maxx - minx);}cout << res << '\n';return 0;
}

闲话

在模拟赛中找到了 \(d\leq 8\) 的同款题目

http://www.hskmm.com/?act=detail&tid=26177

相关文章:

  • 题解:P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II
  • Seismic Unix 基础使用
  • 2025实验室净化厂家/实验室装修厂家/实验室建设厂家权威推荐榜:专业设计与洁净技术实力之选
  • 修改注册表,实现电脑小键盘开机自启(NumLock灯常亮)
  • 完整教程:nav2笔记-250603
  • Bartender打印乱序条码教程
  • 多Agent协作入门:基于A2A协议的Agent通信
  • 时尚产品需求预测与库存优化模型解析
  • 自制带得分和推荐走法的象棋视频
  • DP分析黑科技——闫氏DP分析法
  • MUGEN游戏引擎等一系列相关杂谈
  • # 20232313 2025-2026-1 《网络与系统攻防技术》实验一实验报告 - 20232313
  • 一生一芯学习:PA2:输入输出
  • vector使用中的一个小问题
  • OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering() - 指南
  • 2025.10.7——2绿
  • 完整教程:无人机避障——感知部分(Ubuntu 20.04 复现Vins Fusion跑数据集)胎教级教程
  • 我真的博了
  • 2025.10.6——1绿1蓝
  • 深入解析:人工智能-Chain of Thought Prompting(思维链提示,简称CoT)
  • 年龄排序
  • 二分图最大匹配 输出具体方案
  • 我的联想小新潮7000笔记本的优化
  • Go语言之接口与多态 -《Go语言实战指南》 - 指南
  • 地球科学概论
  • 2025多校冲刺CSP模拟赛4 总结
  • 多路归并、败者树、置换-选择排序、最佳归并树
  • 看vue文档记录(未整理)
  • Spring5笔记
  • 50天50个前端项目 - HTML/CSS和JavaScript实战合集