XDOJ 1257 & HDU 6435 最大化绝对值

ACM

最大化欧拉距离的推广

XDOJ 1257 & HDU 6435 最大化绝对值

这两道题是一类最大化绝对值的题，我们将模型抽象如下：

题目模型抽象

给一些平面上的点，它们可以表示为 $ (x{1} x{2i} \dots x_{di}) $ ，最大化以下值:

$\sum \limits {k=1} ^ {d} {|x{k, i} - x_{k, j}|}$

模型求解

对于特殊情况 ($d=2$, 表示 Manhattan 距离)：

$\sum \limits {k=1} ^ {d} {|x{k, i} - x{k, j}|} = \max \limits{i, j}((x_i + y_i) + \max \limits_j ( -x_j - yj)) + \max \limits{i, j}((x_i - y_i) + \max\limits_j ( -x_j + y_j))$

我们通过上面的式子，可以发现，如果我们 $d$ 是任意数字的话，每个数一定有 $2^d$ 种状态。

状态定义：对于每个数对 $(x{1, i}, x{2,i}, …, x_{d, i})$，每一个数可以取 + 号和 - 号。令取 + 号的二进制位为1，取 - 号的二进制位为 0，则每个状态都可以唯一的映射到 $0 \sim 2^d - 1$ 中。

那么在什么状态下，我们可以构造出最大化的绝对值而且答案是符合要求的呢？

将两个状态加起来等于 $2^d-1$ 就行！

举个例子($d=2$) ,+- 和 -+ 可以表示为上面式子的第二项。

所以我们需要直接将每个状态的最大值算出来，再利用状态和为 $2^d-1$ 的性质解出答案即可。

AC Code

XDOJ 1257

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//#define NOSTDCPP
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 300009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
	
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
	
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
ll ppp[maxn][2];
ll data[50];
int n;
	
int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	ll tmp;
	scan_d(T);
	while(T --)
	{
		scan_d(n);
		for(int i = 1; i <= n; i ++)
			scan_d(ppp[i][0], ppp[i][1]);
		if(n == 1){out_number(0);puts("");continue;}
		for(int i = 0; i < (1 << 2); ++ i)
			data[i] = -1e11;
		for(int i = 1; i <= n; i ++)
		{
			for(int status = 0; status < (1 << 2); ++ status)
			{
				tmp = 0;
				for(int j = 0; j < 2; j ++)
				{
					if(status & (1 << j))
					{
						tmp += ppp[i][j];
					}
					else tmp -= ppp[i][j];
				}
				data[status] = max(data[status], tmp);
			}
		}
		/*
		for(int i = 0; i < (1 << 2); i ++)
			cout << data[i] << ' ';
		cout << endl;
		*/
		ll ans = 0;
		for(int status1 = 0; status1 < (1 << 2); ++ status1)
			for(int status2 = 0; status2 < (1 << 2); ++ status2)
				if(status1 + status2 == (1 << 2) - 1)
					ans = max(ans, data[status1] + data[status2]);
		out_number(ans);
		puts("");
	}
	return 0;
}

HDU 6435

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
//#define NOSTDCPP
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 300009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
	
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
	
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
ll ppp[maxn][6];
ll ze[maxn];
ll datam[50], datab[50];
int n, m, k;
	
int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	ll tmp;
	//scan_d(T);
	scanf("%d", &T);
	while(T --)
	{
		/*
		scan_d(n);
		scan_d(m);
		scan_d(k);
		*/
		scanf("%d %d %d", &n, &m, &k);
		for(int i = 1; i <= n; ++ i)
		{
			//scan_d(ze[i]);
			scanf("%lld", &ze[i]);
			for(int j = 0; j < k; ++ j)
				//scan_d(ppp[i][j]);
				scanf("%lld", &ppp[i][j]);
		}
		for(int i = n + 1, p = 1; p <= m; ++ i, ++ p)
		{
			//scan_d(ze[i]);
			scanf("%lld", &ze[i]);
			for(int j = 0; j < k; ++ j)
				//scan_d(ppp[i][j]);
				scanf("%lld", &ppp[i][j]);
		}
		for(int i = 0; i < (1 << k); ++ i)
			datam[i] = -1e11, datab[i] = -1e11;
		for(int i = 1; i <= n; i ++)
		{
			for(int status = 0; status < (1 << k); ++ status)
			{
				tmp = 0;
				for(int j = 0; j < k; j ++)
				{
					if(status & (1 << j))
					{
						tmp += ppp[i][j];
					}
					else tmp -= ppp[i][j];
				}
				datam[status] = max(datam[status], tmp + ze[i]);
			}
		}
		for(int i = n + 1; i <= n + m; i ++)
		{
			for(int status = 0; status < (1 << k); ++ status)
			{
				tmp = 0;
				for(int j = 0; j < k; j ++)
				{
					if(status & (1 << j))
					{
						tmp += ppp[i][j];
					}
					else tmp -= ppp[i][j];
				}
				datab[status] = max(datab[status], tmp + ze[i]);
			}
		}
		/*
		for(int i = 0; i < (1 << k); i ++)
			cout << datam[i] << ' ' << datab[i] << endl;
		*/
		ll ans = 0;
		for(int status1 = 0; status1 < (1 << k); ++ status1)
			ans = max(ans, datam[status1] + datab[(1 << k) - 1 - status1]);
		out_number(ans);
		puts("");
	}
	return 0;
}

本文标题:XDOJ 1257 & HDU 6435 最大化绝对值

文章作者:Babydragon

发布时间:2018-08-24, 21:24:05

最后更新:2018-08-30, 00:36:07

原始链接:http://baolintian.github.io/2018/08/24/XDOJ-1257-HDU-6435-最大化绝对值/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. XDOJ 1257 & HDU 6435 最大化绝对值
    1. 1.1. 题目模型抽象
    2. 1.2. 模型求解
    3. 1.3. AC Code
      1. 1.3.1. XDOJ 1257
      2. 1.3.2. HDU 6435
{{ live2d() }}