「题解」Codeforces 1612F Armor and Weapons

首先可以不管套件，假定 \(n<m\)，那么答案不超过 \(\mathcal{O}(\log n+\frac{m}{n})\)，也就是先倍增把 \(n\) 造出来，然后一步步造 \(m\)．

答案这么小，那么常见的套路就是把答案放进复杂度里。

然后考虑一个 dp，假设当且在第 \(o\) 轮，令 \(f_i\) 为手中最牛逼的盔甲是 \(i\)，能够拿到最牛逼的武器是 \(f_i\)，想要 dp 出第 \((o+1)\) 轮的 \(f'\)．

不用套件的转移，购买盔甲是 \(f'_j\gets f_i,i\leq j\leq i+f_i\)，购买武器是 \(f'_i\gets f_i+i\)．

用套件的话，那么一定是用 \(i\) 和 \(f_i\)，要不然不会更优，所以也能类似转移。

通过打 tag 然后从后往前取 max 可以做到单次 \(\mathcal{O}(n)\) 转移，那么时间复杂度就是 \(\mathcal{O}(n\log n+m)\)．

const int N=200010;

int n,m,q,x,y,ans,f[N],g[N],fl;
map<int,int>vis[N];

void solve(){
	read(n,m,q);
	if(n>m)swap(n,m),fl=1;
	while(q--)read(x,y),fl?swap(x,y),0:0,vis[x][y]=1;
	f[1]=1;
	for(;f[n]<m;++ans){
		for(int i=1;i<=n;i++)if(f[i]){
			int k=vis[i][f[i]];
			cmax(g[min(n,i+f[i]+k)],f[i]);
			cmax(g[i],min(m,i+f[i]+k));
		}
		for(int i=n;i>=1;i--)f[i]=max(g[i],f[i+1]),g[i]=0;
	}
	cout << ans << '\n';
}