专栏文章

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

BBinah_cyc
P14460题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbznkq
此快照首次捕获于
2025/12/01 23:55
3 个月前
此快照最后确认于
2025/12/01 23:55
3 个月前
查看原文
赛时做法。
首先考虑怎么做到 O(m2)O(m^2) 的复杂度。
考虑 dp，设 dpidp_i 表示已经放置了 ii 个羊毛且现在在位置 00 所需的最小时间。
转移只需要考虑搭最后一次羊毛之前已经搭了多少羊毛。 dpi=min⁡j=0i−1{max⁡(dpj,i×k)+t2×j+t1×(i−j)+t2×i}dp_i=\min_{j=0}^{i-1} \{\max(dp_j,i\times k)+t_2\times j+t_1\times(i-j)+t_2\times i\}
解释一下实际意义。
首先你需要保证在出发之前一共能换出来 ii 块羊毛，所以时间要和 i×ki\times k 取较大值，表示如果羊毛不够的话就等到羊毛足够。然后走到现有的羊毛的尽头，搭羊毛，返回位置 00。
到位置 ii 的答案就是 dpi−i×t2dp_i-i\times t_2，表示你不用再走回到 00 位置了。
考虑优化，先把式子化开。
dpi=min⁡j=0i−1{max⁡(dpj,i×k)+(t2−t1)×j}+(t1+t2)×idp_i=\min_{j=0}^{i-1} \{\max(dp_j,i\times k)+(t_2-t_1)\times j\}+(t_1+t_2)\times i
通过观察这个式子我们可以如果 t2−t1≥0t_2-t_1\ge 0，则随着 jj 增大，内层的贡献单调不降，所以令 jj 取 00 最优。
接下来考虑 t2−t1<0t_2-t_1<0 的情况。
发现内层的 max 十分的恶心，所以我们通过分讨拆掉这个 max。显然 dpdp 数组单调递增，所以取到 i×ki\times k 的 jj 是一个前缀。我们设 pp 表示最大的 jj 满足 dpj<i×kdp_j<i\times k，显然 pp 及以前的位置只与 jj 有关，且 jj 越大答案越小，所以 pp 前的所有决策点都不优。至于 pp 以后的决策点，用一个 multiset 维护所有的决策即可快速得到答案。
CPP
// Problem: P14460 【MX-S10-T1】『FeOI-4』寻雾启示
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14460
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define retunr return
bool startmb;
constexpr int N=1e5+5;
int _,n,k,x,y;

int dp[N];

multiset<int> s;

bool endmb;
main()
{
	cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
	cin.tie(0)->sync_with_stdio(false);
	cin>>_;
	while(_--)
	{
		cin>>n>>k>>x>>y;
		if(y-x>=0)
		{
			for(int i=1;i<=n;i++) cout<<i*k+x*i<<' ';
			cout<<'\n';
		}
		else
		{
			s.insert(0);
			for(int i=1,p=0;i<=n;i++)
			{
				while(p<i&&dp[p]<=i*k) s.extract(dp[p]+(y-x)*p),p++;//维护p的位置
				dp[i]=i*k+(y-x)*(p-1);
				if(s.size()) dp[i]=min(dp[i],*s.begin());//p后的答案
				dp[i]+=(x-y)*i+y*i*2;
				s.insert(dp[i]+(y-x)*i);
			}
			for(int i=1;i<=n;i++) cout<<dp[i]-y*i<<' ';
			cout<<endl;
		}
		s.clear();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...