【ACGO巅峰赛#19】T5灯塔 题解

这种表述的题一眼dp。若没有封印规则，那么设 $f_i$ 为考虑前 $i$ 层的最大价值， $f_i = f_{i-1}+max_{j=1}^{j \le m}v_{i,j}$。而有封印规则后，我们可以设 $f_{i,1/2}$ 为考虑前 $i$ 层后第一或第二大的价值，同时用 $g_{i,1/2}$ 表示 $f_{i,1/2}$ 中对应的选择的列数。如果当前选择的列与 $g_{i,1}$ 相同，则由于封印规则而不能选择 $f_{i,1}$ 转移，只能使用 $f_{i,2}$，否则仍可以选择 $f_{i,1}$ 进行转移。

注意 $m=1$ 时只能选择第一层的那一个，之后的层由于封印规则无法继续选择。

我的代码中将 $f_{i,1/2}$ 与 $g_{i,1/2}$ 合并为一个结构体，从而方便排序。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+10;
int n,m,a[N];
vector<int> vec[N];

struct node{
	int num,id;
}f[N][4],tmp[5];
inline int cmp(node x,node y){
	return x.num>y.num;
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int q1;
	for(int i=1;i<=n;i++){
		vec[i].push_back(0);
		for(int j=1;j<=m;j++){
			cin>>q1;
			vec[i].push_back(q1);
		}
	}
	if(m==1){
		cout<<vec[1][1];
		return 0;
	}
	int maxn = 0;
	for(int i=1;i<=m;i++){
		f[1][3] = {vec[1][i],i};
		sort(f[1]+1,f[1]+4,cmp); // 排序小技巧，使更新第1/2大值时规避复杂的if-else 
	}
	for(int i=2;i<=n;i++){
		int num = 0,maxid,cnt = 0;
		maxn = 0;
		for(int j=1;j<=m;j++){
			if(f[i-1][1].id==j){
				num = f[i-1][2].num+vec[i][j];
			}
			else{
				num = f[i-1][1].num+vec[i][j];
			}
			f[i][3] = {num,j};
			sort(f[i]+1,f[i]+4,cmp);
		}
	}
	maxn = 0;
	for(int i=1;i<=n;i++){
		maxn = max(maxn,f[i][1].num);
	}
	cout<<maxn;
	
	return 0;
}