（dp、贪心）洛谷 P8179 Tyres 题解

题意

有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。

使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1{)}^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。

滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的第一套轮胎不需要进站更换。

为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。

$1\le n,b_i\le 500$，$0\le t\le 500$，$1\le m\le 2\times 10^5$，$1\le a_i\le 10^9$。

思路

注意读题，不是全局的第几圈，而是对于单个轮胎而言的第几圈，因此用胎顺序改变对耗时没有影响。

如果没有换胎这个操作，那么直接用堆维护用胎操作，贪心地每次在优先队列选耗时最少得轮胎跑，然后圈数 $+1$ 扔回队列重新排序。

但是现在有换胎操作所以考虑 dp。设 $f_{i,j}$ 表示前 $i$ 套跑了 $j$ 圈的耗时，$z(i,j)=a_i+b_i\sum _{k=1}^{j-1}{k}^2$。枚举轮胎 $i$ 和圈数 $j$，考虑转移：

• 不选第 $i$ 套胎，即 $f_{i-1,j}$；
• 将第 $i$ 套胎作为第一个使用的胎：$f_{i-1,0}+z(i,j)$；
• 枚举第 $i$ 套胎跑了 $k\in [1,j)$：min⁡k=1j−1{fi−1,j−k+z(i,k)+t}\displaystyle\min_{k=1}^{j-1}\{f_{i-1,j-k}+z(i,k)+t\}k=1minj−1​{fi−1,j−k​+z(i,k)+t}。

三者取最小即可，初始化记得赋极大值，跑 $0$ 圈耗时为 $0$。因为开不下所以滚动数组优化。时间复杂度来到 $O(n{m}^2)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=501,M=1e5+2,inf=0x3f3f3f3f;
int n,m,t;
int a[N],b[N];
ll f[2][M];
ll s2(int x)
{return x*(x+1)*(2*x+1)/6;
}
ll z(int i,int r)
{return r*a[i]+b[i]*s2(r-1);
}
int main()
{scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);memset(f,inf,sizeof(f));for(int i=1;i<=n;i++){ll now=i&1,las=now^1;f[las][0]=0;for(int j=0;j<=m;j++){f[now][j]=min(f[now][j],min(f[las][0]+z(i,j),f[las][j]));//开头不换胎 for(int k=1;k<j;k++)f[now][j]=min(f[now][j],f[las][j-k]+z(i,k)+t);}}ll ans=inf;for(int i=1;i<=n;i++)ans=min(ans,f[i&1][m]);printf("%lld",ans);return 0;
}

考虑优化，这个优化方法很妙是机房的大佬讲的。猜测决策的单调性性质，因为原式有一个平方项，虽然前面加了个 $t$ 破坏了原本贪心的单调性，但是当 $(j-1{)}^{g}et$ 时显然就更大了，因此考虑每个胎在前 $\lceil \sqrt{t}\rceil$ 次 dp，对后续的点就能贪心了，此时取堆头必然最优。取 $B=\sqrt{t_{max}}=23$ 或者 $24,25$ 左右，递推取堆头、维护 $p_i$ 表示从 $B+1$ 开始算起，前 $i$ 次的耗时。答案就是 min⁡i=1min⁡(m,nB){fn,i+pm−i}\displaystyle\min_{i=1}^{\min(m,nB)}\{f_{n,i}+p_{m-i}\}i=1minmin(m,nB)​{fn,i​+pm−i​}。

时间复杂度是 $O(n^{2}B+m\log n)$。

代码中 $z$ 计算函数与上文含义不同，仅计算单次耗时。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=501,M=2e5+2,B=24;
const ll inf=4e18,INf=0x3f3f3f3f;
int n,m,t;
int a[N],b[N];
ll f[2][M],g[N][B+3],p[M];
ll z(ll i,ll loop)
{return a[i]+b[i]*(loop-1)*(loop-1);
}
struct node
{ll id,loop;ll val;
};
bool operator < (node x,node y)
{return x.val>y.val;
}
priority_queue<node>q;
int main()
{scanf("%d%d%d",&n,&m,&t);//为了便于dp，在第1套加了t memset(f,INf,sizeof(f));f[0][0]=0;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);g[i][1]=a[i]+t;//第1圈 for(int j=2;j<=min(m,B);j++)g[i][j]=g[i][j-1]+z(i,j);ll now=i&1,las=now^1;for(int j=0;j<=min(m,i*B);j++)f[now][j]=inf;for(int j=0;j<=min(m,B);j++)//前dp for(int k=0;k<=min(m-j,(i-1)*B);k++)f[now][j+k]=min(f[now][j+k],f[las][k]+g[i][j]);q.push((node){i,B+1,z(i,B+1)});}for(int i=1;i<=m;i++){node tem=q.top();q.pop();p[i]=p[i-1]+tem.val;tem.loop++;tem.val=z(tem.id,tem.loop);q.push(tem);}ll now=n&1,ans=inf;for(int i=1;i<=min(m,n*B);i++)ans=min(ans,f[now][i]+p[m-i]);printf("%lld",ans-t);//第一圈不用换 return 0;
}