背
包
问
题
背包问题
背包问题
正
解
部
分
\color{red}{正解部分}
正解部分
二维偏序问题,
将所 有点 按照
v
v
v 为第一关键字,
w
w
w 为第二关键字 从大到小 排序,
从前往后扫, 离散化坐标, 使用 树状数组 维护
y
y
y 的 前缀最大值, 记为
m
a
x
_
c
u
r
max\_cur
max_cur
对于背包的限制, 将背包按容量 从大到小 排序, 维护一个指针从左往右根据物品的容量往右移动, 记为
t
t
t,
背包从容量大的开始选显然是最优的 .
用
min
(
t
,
m
a
x
_
c
u
r
)
\min(t, max\_cur)
min(t,max_cur) 更新 .
实
现
部
分
\color{red}{实现部分}
实现部分
#include<bits/stdc++.h>
#define reg register
int read(){
char c
;
int s
= 0, flag
= 1;
while((c
=getchar()) && !isdigit(c
))
if(c
== '-'){ flag
= -1, c
= getchar(); break ; }
while(isdigit(c
)) s
= s
*10 + c
-'0', c
= getchar();
return s
* flag
;
}
const int maxn
= 1e5 + 5;
int N
;
int M
;
int Len_2
;
int rl
[maxn
];
int B2
[maxn
];
struct Node
{ int w
, v
; } A
[maxn
];
bool cmp(Node a
, Node b
){ return a
.w
==b
.w
?a
.v
>b
.v
:a
.w
>b
.w
; }
struct Bit_Tree
{
int v
[maxn
], lim
;
void Add(int k
, int x
){ while(k
<=lim
)v
[k
]=std
::max(v
[k
], x
), k
+=k
&-k
; }
int Query(int k
){ int s
= 0; while(k
){ s
= std
::max(v
[k
], s
); k
-= k
&-k
; } return s
; }
} bit_t
;
void Work(){
N
= read();
for(reg
int i
= 1; i
<= N
; i
++) A
[i
].w
= read(), B2
[i
] = A
[i
].v
= read();
std
::sort(A
+1, A
+N
+1, cmp
);
std
::sort(B2
+1, B2
+N
+1), Len_2
= std
::unique(B2
+1, B2
+N
+1) - B2
-1;
for(reg
int i
= 1; i
<= N
; i
++) A
[i
].v
= std
::lower_bound(B2
+1, B2
+Len_2
+1, A
[i
].v
)-B2
;
M
= read();
for(reg
int i
= 1; i
<= M
; i
++) rl
[i
] = read();
std
::sort(rl
+1, rl
+M
+1, std
::greater
<int>());
int t
= 0, Ans
= 0;
bit_t
.lim
= Len_2
; memset(bit_t
.v
, 0, sizeof bit_t
.v
);
for(reg
int i
= 1; i
<= N
; i
++){
while(t
< M
&& rl
[t
+1] >= A
[i
].w
) t
++;
int p
= bit_t
.Query(Len_2
-A
[i
].v
+1), cur
= std
::min(t
, p
+1);
bit_t
.Add(Len_2
-A
[i
].v
+1, cur
); Ans
= std
::max(Ans
, cur
);
}
printf("%d\n", Ans
);
}
int main(){
int T
= read(); while(T
--) Work();
return 0;
}
