【洛谷】P1648 看守（数学）

直接暴力搞\(O(n^2)\)显然是布星滴。

试想，若是一维，最远距离就是最大值减最小值。

现在推广到二维，因为有绝对值的存在，所以有四种情况

\((x1+y1) - (x2+y2), (x1-y1) - (x2-y2), (-x1+y1) - (-x2+y2), (-x1-y1) - (-x2-y2)\)

取最大值即\(1,2\)的曼哈顿距离，于是，枚举\(x,y\)的正负形，各两种，共4种，分别求出那么正负形状态下的最大值和最小值，相减，更新答案。

枚举状态可以利用二进制。

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

#define re register

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

int f[1000010][6];

int n, d, ans, Max, Min, sum;

int main(){

	Open("jail");

	scanf("%d%d", &n, &d);

	for(re int i = 1; i <= n; ++i)

		for(re int j = 0; j < d; ++j)

			scanf("%d", &f[i][j]);

	for(re int i = 1; i < (1 << d); ++i){

       Max = -2147483647, Min = 2147483647;

       for(re int j = 1; j <= n; ++j){

          sum = 0;

	      for(int k = 0; k < d; ++k)

	         if((1 << k) & i)

                sum += f[j][k];

             else sum -= f[j][k];

          Max = max(Max, sum);

          Min = min(Min, sum);

	   }

	   ans = max(ans, Max - Min);

    }

	printf("%d\n", ans);

	return 0;

}

巴特西

【洛谷】P1648 看守（数学）

最新文章

热门文章

巴特西

【洛谷】P1648 看守 （数学）

最新文章

热门文章

【洛谷】P1648 看守（数学）