Codeforces Round 932 (Div. 2) C. Messenger in MAC【挖掘计算公式性质+排序+dp】

原题链接：https://codeforces.com/problemset/problem/1935/C

题目描述：

凯夫特梅鲁姆硕士生援助中心的新信使计划进行更新，开发人员希望在更新中优化显示给用户的信息集。目前共有 n 条信息。每条信息由两个整数 ai 和 bi 表示。读取数字为 p1,p2,…,pk ( 1≤pi≤n ，所有 pi 都是不同的)的信息所花费的时间由公式计算得出：

请注意，读取由**个编号为 p1 的报文组成的报文集所需的时间等于 ap1 。此外，读取一组空信息所需的时间为 0 。

用户可以确定他愿意在信使中花费的时间 l 。信使必须告知用户信息集的最大可能大小，其阅读时间不超过 l 。请注意，信息集的最大大小可以等于 0 。

流行信使的开发人员未能实现这一功能，因此他们要求您解决这一问题。

输入

每个测试由多个测试用例组成。第一行包含一个整数 t ( 1≤t≤5⋅10^4 ) - 测试用例的个数。测试用例说明如下。

每个测试用例的第一行包含两个整数 n 和 l ( 1≤n≤2000 ， 1≤l≤10^9 )--信息数量和用户愿意在信使中花费的时间。

接下来 n 行的 i (th)包含两个整数 ai 和 bi 。( 1≤ai,bi≤10^9 )--第 i 行信息的特征。

保证所有测试用例的 n^2 之和不超过 4⋅10^6 。

输出

对于每个测试用例，输出一个整数 - 一组报文的最大可能大小，其读取时间不超过 l 。

Example
input
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
output
3
1
2
1
0

注

在第一个测试用例中，您可以选取由三条信息组成的一组，其编号分别为 p1=3 、 p2=2 和 p3=5 。读取这组信息所花费的时间等于 a3+a2+a5+|b3−b2|+|b2−b5|=2+1+2+|4−5|+|5−3|=8

在第二个测试用例中，您可以获取一组编号为 p1=1 的信息。读取这组信息所花费的时间等于 a1=4 。

在第五个测试案例中，可以证明不存在这样一个非空的信息集合，其阅读时间不超过 l 。

解题思路：

一眼看上去像背包，但是分析一下发现直接背包时间复杂度非常大，实际上这个题目可以进行常规的线性dp，首先发现代价l非常大，那么代价肯定不能放进状态里面，我们需要求的是最多可以选择多少个位置，并且总代价不超过l，这里涉及到了位置的数量，我们可以尝试把选择的元素个数放进状态，定义f[i][j]表示到了第i个位置，并且已经选择了j个元素的最小代价，但是代价貌似不好计算啊，ai直接把每一个加上就可以了，关键难处理的地方就是bi的代价怎么处理呢，如果我们选择了b中的k个元素，分别为[b1,b2,b3,...,bk]，实际上这里我们要处理的是怎么排列b的顺序使得b的代价最低，证明发现，b按照从小到大的顺序排列时b的总代价最小，下面来证明一下：

首先如果按照从小到大的顺序排列为[b1,b2,b3,...,bk]，代价就是|b1-b2|+|b2-b3|+...+|b(k-1)-bk|

可以把绝对值去掉就是b2-b1+b3-b2+...+bk-b(k-1)，那么中间的项会全部消掉，只留下b1和bk

也就是代价等于bk-b1，如果随意打乱顺序，那么首先bk-b1一定会留下，并且中间一定还会留下一些正的贡献，也就是会使得代价变大，所以b按照从小到大排序时，代价最小。

所以首先我们对于每个位置按照bi从小到大排序，然后考虑dp即可

定义f[i][j]表示到了第i个位置并且选择了j个元素最小代价，a的代价就是所有ai的和，b的代价就是max(bi)-min(bi) (i属于s)，s是我们选中的元素的集合。

初始化：

f[i][1]=c[i].a-c[i].b

if f[i][1]+c[i].b<=l，说明可以只选中i这一个位置

g[i][1]=min(g[i-1][1],f[i][1]）

状态转移：

f[i][j]=min(MAX,g[i-1][j-1]+c[i].a);  //选择当前位置，这里和MAX取min可以防止爆int,就可以不使用longlong了，因为如果f[i][j]超过MAX和置为MAX不影响结果，因为总代价l<MAX,所以超出l的部分是没有意义的。

if(f[i][j]+c[i].b<=l)ans=j;   //说明可以在代价小于等于l的情况下选择j个位置，更新答案

g[i][j]=min(g[i-1][j],f[i][j]);  //g[i-1][j]表示不选择当前位置

最终答案：

最终答案就是满足f[i][j]+c[i].b<=j的最大的j。  //初始化的时候已经减去选中的第一个元素的bi,这里还需要加上当前位置的bi。

时间复杂度：O(n^2)。

空间复杂度：O(n^2)。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
 
const int N=2010,MAX=1e9+10;
 
int T,n,l;
struct Node {
    int a,b;
}c[N];
int f[N][N],g[N][N];
 
void solve()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)cin>>c[i].a,cin>>c[i].b;
    sort(c+1,c+1+n,[&](Node A,Node B){  //按照bi从小到大排序
        return A.b<B.b;
    });
    
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=g[i][j]=MAX;
 
    int ans=0;
    for(int i=1;i<=n;i++)  //初始化
    {
        f[i][1]=c[i].a-c[i].b;   //先减去选择的第一个位置的b,直接放在特定状态的初始化里面，方便后续处理
        if(f[i][1]+c[i].b<=l)ans=1;//说明可以在代价小于等于1的情况下选择j个位置，更新答案
        g[i][1]=min(g[i-1][1],f[i][1]);
    }
 
    for(int j=2;j<=n;j++)
        for(int i=j;i<=n;i++)
        {
            f[i][j]=min(MAX,g[i-1][j-1]+c[i].a);  //选择当前位置，这里和MAX取min可以防止爆int,就可以不使用longlong了
            if(f[i][j]+c[i].b<=l)ans=j;   //说明可以在代价小于等于L的情况下选择j个位置，更新答案
            g[i][j]=min(g[i-1][j],f[i][j]);  //g[i-1][j]表示不选择当前位置
        }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}