文章目录
题面
Sample Input
Sample output
题解
CODE
别的做法
暴力
Dynamic Programming
题面
你想从
N
N
N 个候选人中选 3 个人。
每个人有五个属性
A
i
,
B
i
,
C
i
,
D
i
,
E
i
A_i,B_i,C_i,D_i,E_i
Ai,Bi,Ci,Di,Ei。
一种选人方案假设选了三个人
x
,
y
,
z
x,y,z
x,y,z ，那么这个方案的力量Strength就是
min
{
max
{
A
x
,
A
y
,
A
z
}
max
{
B
x
,
B
y
,
B
z
}
max
{
C
x
,
C
y
,
C
z
}
max
{
D
x
,
D
y
,
D
z
}
max
{
E
x
,
E
y
,
E
z
}
}
\min\left\{\begin{matrix} \max\{A_x,A_y,A_z\}\\ \max\{B_x,B_y,B_z\}\\ \max\{C_x,C_y,C_z\}\\ \max\{D_x,D_y,D_z\}\\ \max\{E_x,E_y,E_z\} \end{matrix}\right\}
min⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧max{Ax,Ay,Az}max{Bx,By,Bz}max{Cx,Cy,Cz}max{Dx,Dy,Dz}max{Ex,Ey,Ez}⎭⎪⎪⎪⎪⎬⎪⎪⎪⎪⎫
求力量Strength最大的方案的力量Strength是多少。
输入分别给出
N
N
N 和
N
N
N 行整数
A
i
,
B
i
,
C
i
,
D
i
,
E
i
A_i,B_i,C_i,D_i,E_i
Ai,Bi,Ci,Di,Ei。
输出一行一个整数表示答案。
3
≤
N
≤
3000
,
1
≤
A
i
,
B
i
,
C
i
,
D
i
,
E
i
≤
1
0
9
3\leq N\leq 3000,1\leq A_i,B_i,C_i,D_i,E_i \leq 10^9
3≤N≤3000,1≤Ai,Bi,Ci,Di,Ei≤109.
Sample Input
10
6 7 5 18 2
3 8 1 6 3
7 2 8 7 7
6 3 3 4 7
12 8 9 15 9
9 8 6 1 10
12 9 7 8 2
10 3 17 4 10
3 1 3 19 3
3 14 7 13 1
Sample output
10
题解
首先，我们会想到一种
N
3
N^3
N3 的暴力做法。
之所以这样过不了，是因为我们想知道的力量与每个属性都有关，又跟每个属性的最大值有关，属性不同的有
N
N
N 个人，因此时间复杂度便上天。
为了消除这些限制，同时发现这道题相当于求最小值前提下的最大值，于是我们不妨想想二分。
我们二分一个答案，表示每项属性的最大值都要大于等于这个值。那么此时，相当于定了一个标准——一个属性大于等于这个值为合格，否则不合格。要求是要让选出的三个人中每项属性都至少有一个人合格。此时，由于我们想知道的是否合法与每个属性的合格与否有关，而每个属性只有两种情况：合格/不合格，因此，把每项属性合格情况(一共
2
5
2^5
25 种)相同的合并到一起，我们相当于只有
2
5
=
32
2^5=32
25=32 位候选人了！然后再随便用一个三次方的暴力(时间
2
15
2^{15}
215)就可以解决问题，或者稍加dp优化变成平方，跑到最优解 6~8 ms。
时间复杂度
O
(
log
X
(
5
N
+
2
10
)
)
O(\log X(5N+2^{10}))
O(logX(5N+210))
CODE
#include<map>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 3005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int a[MAXN][10];
bool dp[4][1<<5|5];
bool check(int val) {
memset(dp,0,sizeof(dp));
for(int i = 1;i <= n;i ++) {
int S = 0;
for(int j = 1;j <= 5;j ++) {
if(a[i][j] >= val) S |= (1<<(j-1));
}
dp[1][S] = 1;
}
dp[1][0] = dp[2][0] = dp[3][0] = 1;
for(int kk = 1;kk <= 2;kk ++) {
for(int i = 0;i < (1<<5);i ++) {
if(dp[kk][i])
for(int j = 0;j < (1<<5);j ++) {
dp[kk+1][i|j] |= dp[1][j];
}
}
}
return dp[3][(1<<5)-1];
}
int main() {
n = read();
for(int i = 1;i <= n;i ++) {
for(int j = 1;j <= 5;j ++) {
a[i][j] = read();
}
}
int ans = 0;
for(int i = 30;i >= 0;i --) {
if(ans+(1<<i) <= 1000000000 && check(ans+(1<<i))) ans += (1<<i);
}
printf("%d\n",ans);
return 0;
}
别的做法
暴力
有一个
15
∗
N
2
15*N^2
15∗N2 的做法，详见PPL的博客
其核心思想在于：最后的方案中，不可能三个人都贡献了
≥
2
\geq2
≥2 个最大值，因此一定有一个人贡献了
≤
1
\leq 1
≤1 个最大值，那么不妨就令这个人为这个属性中可以选的最大的一个人，于是暴力可以少一维。
Dynamic Programming
官方题解中的第二种做法。
题意可以转化为：你先选三个候选人
x
,
y
,
z
x,y,z
x,y,z，然后每个属性你都在三个人中选一个人的拿出来，要让这五个数的最小值最大。不难发现这样和原题面（贪心地选最大的）最终答案是一样的。
那么就可以设计出一个 DP：
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k] 表示前
i
i
i 个人中选了
j
j
j 个人(
j
≤
3
j\leq3
j≤3) ，属性状态为
k
k
k(
k
≤
2
5
k\leq 2^5
k≤25) 时的最大答案（
k
k
k 的二进制第
i
i
i 位表示第
i
i
i 种属性是否已经选了人），转移的时候保证每种属性只选一个人。转移可以
O
(
5
)
O(5)
O(5) 。
那么总时间就是
O
(
15
N
∗
2
5
)
O(15N*2^5)
O(15N∗25)。
官方代码
