[CF1826E] Walk the Runway 题解

首先可以直接 dp，先按

r_{1,i}

排序，设

f_i

表示考虑到第

i

个人且选择第

i

个人的最大价值，则转移为

\displaystyle f_i=p_i+\max_{j<i,j\isin G_i}f_{j}

，其中

G_i

表示所有满足

\forall 1\le k\le m,r_{k,i}>r_{k,j}

的

j

构成的集合。注意到整个 dp 是

\mathcal{O}(n^2)

的，于是只需要快速求出

G_i

即可。

r_{k,i}>r_{k,j}

的

(i,j)

在

k

不同时很分散，难以维护，考虑一些暴力的做法。

若

m=1

，则问题是简单的，维护一个集合

S

，初始为空，按

r_{1,i}

从小到大往

S

中加入

i

，则

G_x

就可以视作加入

x

之前的集合

S

，不妨设此时的集合

S

为

T_{1,x}

。

接下来考虑

m

更大时的做法，我们一样可以对每一行维护

S

，然后求出所有的

T_{i,j}

，则

G_{x}=\bigcap_{i=1}^m T_{i,x}

。

直接将

S,T_{i,j},G_i

视作 bitset 即可维护。具体实现时不需要存储

T_{i,j}

，只需要对每一行动态维护

S

并记录

G_i

即可。还需要注意

r

相等的情况。

时间复杂度

\mathcal{O}(\frac{n^2m}{\omega})

，其中

\omega=64

，CF 把时限卡这么满也是有点少见了。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=5007;
ll n,m,a[maxn],f[maxn],v[maxn],id[maxn],ans;
bitset<maxn> stt,g[maxn];
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>m>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++) g[i][j]=1;
    for(ll i=1;i<=m;i++){
        stt.reset();
        for(ll j=1;j<=n;j++) cin>>v[j],id[j]=j;
        sort(id+1,id+1+n,[&](ll x,ll y){return v[x]<v[y];});
        for(ll l=1,r;l<=n;l=r+1){
            for(r=l;r<=n;r++){
                g[id[r]]&=stt;
                if(r==n||v[id[r]]!=v[id[r+1]]) break;
            }
            for(ll j=l;j<=r;j++) stt[id[j]]=1; 
        }
    }
    for(ll t=1,i,j;t<=n;t++){
        i=id[t],f[i]=a[i];
        for(ll x=1;x<t;x++){
            j=id[x];
            if(g[i][j]) f[i]=max(f[i],f[j]+a[i]);
        }
        ans=max(ans,f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

[CF1826E] Walk the Runway 题解

文章操作

相关推荐

评论

[CF1826E] Walk the Runway 题解