自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:36:39，当前版本为作者最后更新于2022-03-02 08:48:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

EZEC R11 Problem C。

Div.1 预期通过 $50$，实际通过 $6$。

Div.2 预期通过 $30$，实际通过 $1$。

本来是想用这个题让大家笑一笑然后去轻松地开始这场比赛，结果似乎没有人笑……

关注嘉然，顿顿解馋！

Hint

每套轮胎一定只会使用一个连续的区间。

不然把这两段放一起能省一次换胎的时间。

Solution 1

我会模拟！

第 $i$ 圈需要 $a_1+b_1(i-1)^2$ 的时间，暴力算出每一圈的时间加起来就行了。

可以通过 Subtask $1$。

Solution 2

我会贪心！

如果 $t=0$，那么我们相当于每圈都可以自己选一套轮胎。

每套轮胎的单圈时间随着圈数上升，也就是一个单调的函数。

于是我们需要归并这 $n$ 个序列并求出前 $m$ 项。

使用一个堆即可，时间复杂度 $O(m\log n)$。

可以通过 Subtask $1,3,4$。

对于 Subtask $2$，如果你枚举 $2^n$ 个子集为至少使用一次的轮胎也可以通过。

Solution 3

我会暴力 dp！

考虑枚举第 $i$ 套轮胎跑 $0\sim m$ 圈的代价，问题变为分组背包，时间复杂度 $O(nm^2)$。

可以通过 Subtask $1,2$。

Solution 4

我会决策单调性优化！

直接优化前面的背包问题，时间复杂度可以降低到 $O(nm\log m)$。

还是只能通过 Subtask $1,2$。

这里忘记给一档分了，但是如果你在 $nm$ 比较大的时候直接跑 Solution $2$ 可以直接通过。

这种做法是可以卡的，直接将卡堆贪心的测试点中放几个 $(1,500)$ 再整体平移 $a_i$ 就可以了，但是由于没有验题人写这个算法（大家都认为这个算法的实现可能比本题正解更难）就没有卡掉，向大家道歉。

不过这样是不是也避免了一些人去写 $O(nm)$ 算法呢？

Solution 5

我会找性质！

不妨把换胎时间加到第一圈的时间上，这样就不存在“换胎”这个操作了。

注意到我们不能使用堆贪心是因为价格不单调，考虑强行将价格变为单调。

我们考虑记 $S=\lceil\sqrt t\rceil$。不难发现对于每套轮胎，$S$ 圈以后的价格一定比 $S$ 圈之前的价格贵，并且也是单调的，我们可以将两部分分开决策。

于是我们对于每套轮胎的前 $S$ 圈做一个 dp，$S$ 圈之后用堆贪心，合并两边的结果即可。

如果使用 Solution $2,3$ 的方法，时间复杂度为 $O(n^2t+m\log n)$。

如果使用 Solution $2,4$ 的方法，时间复杂度为 $O(n^2\sqrt t\log(n\sqrt t)+m\log n)$。

两者都可以通过。

Code

//And in that light,I find deliverance.
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int B=25;
int f[503][33],g[13003],h[200003],a[503],b[503],c[503];
struct cmp
{
	bool operator()(const int&x,const int&y)
	{
		return (a[x]+b[x]*c[x]*c[x]>a[y]+b[y]*c[y]*c[y])||
			(a[x]+b[x]*c[x]*c[x]==a[y]+b[y]*c[y]*c[y]&&x>y);
	}
};
priority_queue<int,vector<int>,cmp> q;
signed main()
{
	int n=read(),m=read(),d=read(),s=0;
	for(int i=1; i<=n; ++i) 
	{
		a[i]=read(),b[i]=read(),c[i]=25,q.push(i);
		f[i][1]=a[i]+d;
		for(int j=2; j<=B; ++j) f[i][j]=f[i][j-1]+a[i]+b[i]*(j-1)*(j-1);
	}
	memset(g,0x3f,sizeof(g)),g[0]=0;
	for(int i=1; i<=n; ++i)
	{
		s=min(m,s+B);
		for(int j=s; j>=0; --j)
			for(int k=0; k<=B&&k<=j; ++k)
				g[j]=min(g[j],g[j-k]+f[i][k]);
	}
	for(int i=1; i<=m; ++i)
	{
		int x=q.top();
		q.pop(),h[i]=h[i-1]+a[x]+b[x]*c[x]*c[x],
		++c[x],q.push(x);
	}
	int ans=0x3f3f3f3f3f3f3f3f;
	for(int i=0; i<=s&&i<=m; ++i) ans=min(ans,g[i]+h[m-i]);
	printf("%lld\n",ans-d);
	return 0;
}