题解：P14460 【MX-S10-T1】『FeOI-4』寻雾启示

简单题。

设

f(i)

表示

i

的答案。

则有转移：

f(i) = \min_{j < i} f(j) + t_2 \cdot j + \max(0,i \cdot k - (f(j) + t_2 \cdot j)) + t_2 \cdot j + t_1 \cdot (i - j)

发现带

j

的都是简单的，线段树一下就行，唯一就是

\max

那个式子，由于

f

是单增的，所以可以二分找到最后一个满足

i \cdot k - (f(j) + t_2 \cdot j) \ge 0

的位置，然后分别维护两颗线段树，一颗不用关系

\max

的式子，另一颗对于点

i

有额外的

f(i) + t_2 \cdot i

的贡献，时间复杂度

\mathcal O(Tn\log n)

。

代码

CPP

#include <bits/stdc++.h>

constexpr int N = 1e5 + 5;

long long f[N],m,k,t1,t2;

inline void chkmin(long long & x,long long y){
	x = (y < x ? y : x);
}
struct segment_tree{
	long long mn[N << 2];
	inline int ls(int x){
		return x << 1;
	} 
	inline int rs(int x){
		return x << 1 | 1;
	}
	inline void push_up(int x){
		mn[x] = std::min(mn[ls(x)],mn[rs(x)]);
	}
	inline void build(int u,int l,int r){
		mn[u] = 1e18;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(ls(u),l,mid);
		build(rs(u),mid + 1,r);
	}
	inline void update(int u,int l,int r,int x,long long val){
		if(l == r){
			mn[u] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) update(ls(u),l,mid,x,val);
		else update(rs(u),mid + 1,r,x,val);
		push_up(u);
	}
	inline long long query(int x,int l,int r,int ql,int qr){
		if(ql <= l && qr >= r){
			return mn[x];
		}
		long long Min = 1e18,mid = (l + r) >> 1;
		if(ql <= mid) chkmin(Min,query(ls(x),l,mid,ql,qr));
		if(qr > mid) chkmin(Min,query(rs(x),mid + 1,r,ql,qr));
		return Min;
	}
}T1,T2;
inline void solve(){
	std::cin >> m >> k >> t1 >> t2;
	f[0] = 0;
	T1.build(1,1,m);
	T2.build(1,1,m);
//	for(int i = 1; i <= m; ++ i){
//		f[i] = 1e18;
//		long long t = 1ll * i * k;
//		for(int j = 0; j < i; ++ j){
//			long long reach = f[j] + 1ll * t2 * j;
//			chkmin(f[i],reach + std::max(0ll,t - reach) + t2 * j + t1 * (i - j));
//		}
//	}
	for(int i = 1; i <= m; ++ i){
		f[i] = 1e18;
		long long t = 1ll * i * k;
		
		for(int j = 0; j <= 0; ++ j){
			long long reach = f[j] + 1ll * t2 * j;
			chkmin(f[i],reach + std::max(0ll,t - reach) + t2 * j + t1 * (i - j));
		}
		int l = 1,r = i - 1,ans = 0;
		while(l <= r){
			int mid = (l + r) >> 1;
			long long reach = f[mid] + mid * t2;
			if(reach <= t){
				l = mid + 1;
				ans = mid;
			}else{
				r = mid - 1;
			}
		}
		if(ans > 0){
			chkmin(f[i],t + t1 * i + T1.query(1,1,m,1,ans));
		}
		if(ans + 1 < i){
			chkmin(f[i],t1 * i + T2.query(1,1,m,ans + 1,i - 1));
		}
		long long reach = f[i] + 1ll * t2 * i;
		T1.update(1,1,m,i,t2 * i - t1 * i);
		T2.update(1,1,m,i,reach + t2 * i - t1 * i);
	}
	for(int i = 1; i <= m; ++ i){
		std::cout << f[i] << ' ';
	}
	std::cout << '\n';
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int T;
	std::cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

题解：P14460 【MX-S10-T1】『FeOI-4』寻雾启示

文章操作

相关推荐

评论

题解：P14460 【MX-S10-T1】『FeOI-4』寻雾启示