前言

被同学强行拉过来补ABC，然后他不会G，我一看啊我也不会，于是就有了这篇题解

虽然正确率很高，但是这篇题解不是正解，如果有hack可以联系管理撤下题解。

题意

给你一个序列 $now$，初始它均为 $1$。你可以花费 $c[i]$ 的代价把 $i$ 这个位置增加 $1$。

再给你 $m$ 个目标，第 $i$ 个目标是一个数组 $l[i][j]$，代表如果 $now$ 每个位置都比 $l[i]$ 对应位置大，那么可以得到 $a[i]$ 的收益。

我们要求出最大净收益。

解法

我们发现数据范围奇小无比。所以考虑进行乱搞。

考虑按照净收益对目标排序，然后顺序完成目标，在中途记录答案并更新最大值。

具体实现参考核心代码：

1
2
3
4
5
bool cmp(int x,int y){
    int ansl=0,ansr=0;
    for(int i=1;i<=n;++i)ansl+=(max(0ll,l[x][i]-now[i]))*c[i],ansr+=(max(0ll,l[y][i]-now[i]))*c[i];
    return a[x]-ansl<a[y]-ansr;
}

时间复杂度为 $O(m^2n \log m)$。

然后，这个做法光荣地被卡了一个点。

你不要火大。

然后你额外乱随一堆目标序列，然后直接尝试顺序达成，更新最大值即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[55],c[55],l[55][55],now[55],ans,sans;
vector<int>fuc;
bool cmp(int x,int y){
    int ansl=0,ansr=0;
    for(int i=1;i<=n;++i)ansl+=(max(0ll,l[x][i]-now[i]))*c[i],ansr+=(max(0ll,l[y][i]-now[i]))*c[i];
    return a[x]-ansl<a[y]-ansr;
}
mt19937 rd((unsigned long long)new char);
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>c[i],now[i]=1;
    for(int i=1;i<=m;++i)cin>>a[i],fuc.push_back(i);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)cin>>l[i][j];
    for(int i=1;i<=m;++i){
        sort(fuc.begin(),fuc.end(),cmp);
        int t=fuc.back(),sum=0;
        for(int j=1;j<=n;++j)sum+=c[j]*(max(0ll,l[t][j]-now[j]));
        sum=a[t]-sum;
        for(int j=1;j<=n;++j)now[j]=max(now[j],l[t][j]);
        ans+=sum;sans=max(sans,ans);fuc.pop_back();
    }
    for(int tm=1;tm<=102624;++tm){
        for(int i=1;i<=n;++i)now[i]=1;
        for(int i=1;i<=m;++i)fuc.push_back(i);
        ans=0;
        shuffle(fuc.begin(),fuc.end(),rd);
        for(int i=1;i<=m;++i){
            int t=fuc.back(),sum=0;
            for(int j=1;j<=n;++j)sum+=c[j]*(max(0ll,l[t][j]-now[j]));
            sum=a[t]-sum;
            for(int j=1;j<=n;++j)now[j]=max(now[j],l[t][j]);
            ans+=sum;sans=max(sans,ans);fuc.pop_back();
        }
        fuc.clear();
    }
    cout<<sans<<'\n';
    return 0;
}

这么做的时间复杂度为 $O(m^2n \log m + Tn(n+m))$，其中 $T$ 为后面一部分的随机次数。实际测试取 $T=102624$，可以稳过。