CF1936C Pokémon Arena 题解

link T2 desu

有 $n$ 只宝可梦，初始第 $1$ 只在竞技场上。每只宝可梦有 $m$ 个属性，第 $i$ 只宝可梦的第 $j$ 个属性为 $a_{i,j}$，雇佣费用为 $c_i$。

允许操作：

1. 属性提升：选 $i, j, k$，将 $a_{i,j}$ 永久增加 $k$，费用为 $k$

2. 雇佣对战：选 $i, j$，雇佣第 $i$ 只宝可梦与当前场上宝可梦比较属性 $j$

   • 若 $a_{i,j} \ge$ 当前场上宝可梦的属性 $j$，则 $i$ 获胜并留在场上
   • 费用为 $c_i$

目标：让第 $n$ 只宝可梦站在竞技场上。求最小总费用。

---

观察一下可以发现一个宝可梦的一种属性是没有多次使用的必要的。

因为是永久修改。直接在一开始就修改至最后一次使用的值就会更优。

那么我们就可以直接最短路。

对于同一属性类型 $j$，显然所有宝可梦都可以基于 $j$ 属性连上 $n(n-1)$ 条边。但这样太多了。

考虑将 $a_{i,j}$ 排序之后按照前缀链优化。相当于给 $j$ 类型搞一个专门的梯子上下。然后修改权值保存在链的每两个相邻节点中。

但是这样子会导致 $c_i$ 判定出现问题。如果在点上保存 $c_i$，会使得经过这个点但对战目标不是这个点的同样会被收取费用。

解决方法是不在原先的 $1\sim n$ 的点建梯子，而是专门开出 $n$ 个点作为梯子。如果确定在某个点结束修改，就退出梯子即可。

只需要在退出梯子的位置存 $c_i$ 就不会有问题了。

如图所示：

（这里是无向边，纯粹是不想画箭头awa，毕竟都是双向有向边嘛）

代码

int n,m,nm;
ll c[maxn];
vector<ll> a[maxn];//正常的a
vector<PII> b[maxn];//按j维护的a
void input(){
	n=read();m=read();
	nm=n*(m+1);
	for(int i=1;i<=n;++i) c[i]=read();
	for(int i=1;i<=n;++i){
		a[i].emplace_back(0);
		for(int j=1;j<=m;++j) a[i].emplace_back(read());
	}
	for(int j=1;j<=m;++j){
		b[j].push_back({-inf,0});
		for(int i=1;i<=n;++i){
			b[j].push_back({a[i][j],i});
		}
	}
}


struct Edge{
	int _this,nxt;
	ll w;
	Edge(){
		_this=nxt=w=0;
	}
}edge[maxn<<1];
int headnxt[maxn],idx;
void merge(int from,int to,ll w){
	edge[++idx]._this=to;
	edge[idx].w=w;
	edge[idx].nxt=headnxt[from];
	headnxt[from]=idx;
}
void make_edge(int col){//制定一个颜色，构建一个梯子
	sort(b[col].begin(),b[col].end());
	for(int i=2;i<=n;++i){
		int u=col*n+i-1,v=col*n+i;
		ll w=b[col][i].first-b[col][i-1].first;
		merge(u,v,0);
		merge(v,u,w);
	}
	for(int i=1;i<=n;++i){
		int u=col*n+i,v=b[col][i].second;
		merge(u,v,c[v]);
		merge(v,u,0);
	}
}


/*
后面跑dij即可
*/

sub