题解：P8179 「EZEC-11」Tyres

Aegleseeker_ · 2025-11-13 11:08:10 · 题解

很有意思的题。

先考虑 t=0 怎么做，此时对于每个轮胎，其消耗代价是随跑的圈数单调上升的，因此可以直接贪心。将每个轮胎与其要跑的圈数放进堆里维护即可。可以做到 O(m\log n)。

再考虑 m 和 n 同阶怎么做，令 f_{i,j} 代表考虑到前 i 个轮胎、目前已经跑了 j 圈的最小代价。转移就是一个朴素的背包：

其中 c(i,j) 代表第 i 个轮胎一共跑了 j 圈的代价。这样直接 dp 就是 O(nm^2) 的了，如果注意到转移具有决策单调性的话，也可以二分决策点，做到 O(nm\log m)。

现在我们考虑正解。由于 t\neq 0，因此对于每个轮胎，其消耗代价关于跑的圈数的函数并不是呈单调的，而是在 j=1 时出现了 a_i+t 的浮点。为了使这个函数单调，我们考虑根号分治，找到后面第一个代价超过浮点代价的位置 B，那么对于 j>B 的部分仍满足单调性，我们可以直接二分；对于 j\le B 的部分不满足单调行，我们用 dp，限制下不能取超过 B 个。最后将 dp 结果与贪心结果合并取 \min 即可。

注意到当 B 取 \sqrt t 时，这一性质恰好满足！复杂度降为 O(n^2t+m\log n)，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int M=2e5+5;
#define int long long
int n,m,t,B;
int a[N],b[N];
long long f[N][N*25],g[M],s[M],ans=4e18;
long long calc(int i,int j){
    return a[i]*j+b[i]*s[j-1];
}
struct node{
    int i,j;
    long long val;
    bool operator <(const node &b)const{
        return val>b.val;
    }
};
priority_queue<node> q;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<M;i++){
        s[i]=s[i-1]+i*i;
    }
    cin>>n>>m>>t;
    B=ceil(sqrt(t));
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N*25;j++){
            f[i][j]=4e18;
        }
    }
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(m,B*i);j++){
            for(int k=max(0ll,j-B);k<=j;k++){
                f[i][j]=min(f[i][j],f[i-1][k]+(k!=j&&k!=0)*t+calc(i,j-k));
            }
        }
    }
    for(int i=1;i<=n;i++){
        q.push(node{i,B+1,a[i]+1ll*b[i]*B*B});
    }
    for(int i=1;i<=m;i++){
        node u=q.top();
        q.pop();
        g[i]=g[i-1]+u.val;
        u.j++,u.val=a[u.i]+1ll*b[u.i]*(u.j-1)*(u.j-1);
        q.push(u);
    }
    for(int i=0;i<=min(m,B*n);i++){
        ans=min(ans,f[n][i]+g[m-i]);
    }
    cout<<ans;
    return 0;
}