[CF1826E] Walk the Runway 题解
aeiouaoeiu
·
·
题解
首先可以直接 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 即可。
若 $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 把时限卡这么满也是有点少见了。
::::info[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;
}
```
::::