盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5125 magic balls(LIS+dp+树状数组)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5125

题意

有两排球,每排有n个。每个球有一个体积vi。现在要从第一排中选一些球,使得这些球的体积为最长上升序列。你可以使用m次魔法,每次可以把第一排的一个球换成第二排对应位置的球。求最长的子序列长度。

思路

最长上升子序列可以用树状数组或者线段树维护。dp[i]表示以第i个数结尾的最长上升子序列长度。每加入一个新数,查询比该数小的数的dp最大值mx,用mx+1更新该数的dp值
回到这道题,我们先对球的体积进行离散化。用dp[i][j]表示到i个位置,使用了j次交换的最值,那么有如下转移方程:
dp[i][j] = max(dp[k][j] + 1) 其中k<i,且s[j][k]<a[i]
dp[i][j] = max(dp[k][j - 1] + 1) 其中k<i,且s[j-1][k]<b[i]
其中s[j]表示交换了j次时,需要维护的树状数组的情况
这道题用线段树维护常数太大,容易T。

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 1010;
int a[N], b[N], c[N * 2], n, m, cnt;
int bit[N][N * 2];
inline int lowbit(int x) {
return x & (-x);
}
void add(int i, int p, int v) {
while(p <= cnt) {
bit[i][p] = max(bit[i][p], v);
p += lowbit(p);
}
}
int sum(int i, int p) {
int res = 0;
while(p > 0) {
res = max(res, bit[i][p]);
p -= lowbit(p);
}
return res;
}
int main () {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
c[0] = 0;
cnt = 1;
for (int i = 0; i < n; i++) {
scanf("%d%d", a + i, b + i);
c[cnt++] = a[i];
c[cnt++] = b[i];
}
sort(c, c + cnt); cnt = unique(c, c + cnt) - c;
for (int i = 0; i < n; i++) a[i] = lower_bound(c, c + cnt, a[i]) - c;
for (int i = 0; i < n; i++) b[i] = lower_bound(c, c + cnt, b[i]) - c;
for (int i = 0; i <= m; i++)
for (int j = 0; j <= cnt; j++) bit[i][j] = 0;
int mx = 0;
for (int i = 0; i < n; i++)
for (int j = min(i + 1, m); j >= 0; j--) {
int k = sum(j, a[i] - 1) + 1;
mx = max(mx, k);
add(j, a[i], k);
if (j) {
k = sum(j - 1, b[i] - 1) + 1;
mx = max(mx, k);
add(j, b[i], k);
}
}
printf("%d\n", mx);
}
return 0;
}