题目描述

难度分:$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;
}