题解：CF1826E Walk the Runway
Gao_l
·
·
题解
传送门
很容易想到 O(n^2m) 的 dp 做法。
转移方程为：$dp_i=dp_j+p_i$（如果可以转移）。
code:
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int p[N],r[N][N];
bool can[N][N];
int dp[N];
int cnt[N];//储存映射关系
int n,m;
bool cmp(int x,int y){
return r[1][x]<r[1][y];
}
signed main(){
cin >> m >> n;
for(int i=1;i<=n;i++)cin >> p[i];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin >> r[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
can[i][j]=true;
for(int k=1;k<=m;k++){
if(r[k][i]<=r[k][j]){
can[i][j]=false;
break;
}
}
}
}
for(int i=1;i<=n;i++){
cnt[i]=i;
dp[i]=p[i];//自己
}
sort(cnt+1,cnt+1+n,cmp);//将一维单调 可以证明 i 只能从 1~i-1转移
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(can[cnt[i]][cnt[j]]){//如果可以转移
dp[cnt[i]]=max(dp[cnt[i]],dp[cnt[j]]+p[cnt[i]]);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout << ans << "\n";
return 0;
}
```
但是很明显过不了。
考虑 bitset 优化，开 $n$ 个长度为 $n$ 的 bitset 数组 $b$。
$b_{i,j}=1$ 时表示可以从 $j$ 转移到 $i$。
然后，考虑每一维的预处理将逐位枚举变成 $\&$ 操作，此时时间复杂度从 $O(m)$ 降为 $O(\frac{m}{w})$（此时 $w=32$）。
这时，我们就可以用 $O(\frac{n^2m}{w})$（此时 $w=32$）的时间复杂度预处理出 $b$。
然后通过 dp 以 $O(nm\log_n)$ 的时间复杂度求出答案。
总时间复杂度：
$$O(\frac{n^2m}{w}+nm\log_2n)$$
AC code：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int n,m;
int p[N];
int a[N][N];
int cnt[N];
int nid;
bool cmp(int x,int y){
return a[nid][x]<a[nid][y];
}
bitset<5005>b[N],now;
int dp[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> m >> n;
for(int i=1;i<=n;i++){
cin >> p[i];
cnt[i]=i;
b[i].set();//初始为全1
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin >> a[i][j];
}
}
for(int k=1;k<=m;k++){
nid=k;
now.reset();
sort(cnt+1,cnt+1+n,cmp);//对第k维排序
for(int i=1,j;i<=n;i++){
j=i;
while(j<n&&a[k][cnt[j]]==a[k][cnt[j+1]])j++;//特判相等的情况
for(int l=i;l<=j;l++){
b[cnt[l]]&=now;
}
for(int l=i;l<=j;l++){
now[cnt[l]]=1;
}
i=j;
}
}
int ans=0;
for(int i=1;i<=n;i++){
dp[cnt[i]]=p[cnt[i]];
ans=max(ans,dp[cnt[i]]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(b[cnt[i]][cnt[j]]){
dp[cnt[i]]=max(dp[cnt[i]],dp[cnt[j]]+p[cnt[i]]);
ans=max(ans,dp[cnt[i]]);
}
}
}
cout << ans << "\n";
return 0;
}
```