题目描述
难度分:$1800$
输入$T(\leq 5 \times 10^4)$表示$T$组数据。所有数据的$n^2$之和$\leq 4 \times 10^6$。
每组数据输入$n(1 \leq n \leq 2000)$,$l(1 \leq l \leq 10^9)$和长为$n$的数组,其中第$i$个元素是数对$(a_i, b_i)$,范围$[1,10^9]$。
你可以打乱这$n$个元素的顺序。选出数组中的一个子序列(不一定连续),要求满足
$sum($子序列中的$a) + sum($子序列中相邻两个$b$的绝对差$) \leq l$
输出子序列长度的最大值。
输入样例
5
5 8
4 3
1 5
2 4
4 3
2 3
1 6
4 10
3 12
4 8
2 1
2 12
5 26
24 7
8 28
30 22
3 8
17 17
5 14
15 3
1000000000 998244353
179 239
228 1337
993 1007
输出样例
3
1
2
1
0
算法
动态规划
没昨天那个$1400$的题思维难度高,$n \leq 2000$感觉就是动态规划,往这上面靠就能做出来。先对$(a_i,b_i)$按照$b_i$排序,然后进行DP
,这样就不用考虑绝对值了,肯定是后一个$b$大于等于前一个$b$。
状态定义
$f[i][j]$表示选择$i$,且一共选择$j$个二元组的情况下,能够达到的最小$\Sigma_{k=1}^{j} a_{i_k}+\Sigma_{k=1}^{j-1}|b_{i_k}-b_{i_{k-1}}|$,其中$i_k$表示选出来$j$个二元组中的第$k$个。在这个定义下,DP
完成后,遍历$i \in [1,n]$,对于固定的$i$遍历$j \in [1,i]$,最大满足$f[i][j]$的$j$就是答案。
状态转移
双重循环遍历$i \in [1,n]$,$j \in [1,n]$,然后考虑倒数第二个位置$last \lt i$,有状态转移方程
$f[i][j]=min_{last \lt i}f[last][j-1]+a_{i}+b_{i}-b_{last}$
前缀最小值优化
此时如果遍历$last$,那整个算法的时间复杂度就是$O(n^3)$,不可接受。但是我们发现,$f[last][j-1]-b_{last}$可以放在一起,因此没有必要去遍历$last$,只要维护一个前缀最小值就可以让状态转移从$O(n)$变成$O(1)$。
复杂度分析
时间复杂度
状态数量是$O(n^2)$,前缀最值优化后,单次转移的时间复杂度为$O(1)$。因此,整个算法的时间复杂度为$O(n^2)$。
空间复杂度
空间瓶颈就是DP
矩阵$f$,所以额外空间复杂度为$O(n^2)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010;
LL f[N][N];
int t, n, l;
struct Node {
int a, b;
bool operator<(const Node other) const {
return b < other.b;
}
} nodes[N];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &l);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &nodes[i].a, &nodes[i].b);
}
sort(nodes + 1, nodes + n + 1);
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
f[i][j] = 1e13;
}
}
for(int i = 1; i <= n; i++) {
f[i][0] = 0;
}
for(int j = 1; j <= n; j++) {
LL minpre = f[0][j - 1];
for(int i = 1; i <= n; i++) {
if(j == 1) {
f[i][j] = nodes[i].a;
}else {
f[i][j] = minpre + nodes[i].a + nodes[i].b;
}
minpre = min(minpre, f[i][j - 1] - nodes[i].b);
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
if(f[i][j] <= l) {
ans = max(ans, j);
}
}
}
printf("%d\n", ans);
}
return 0;
}