题解 P8179

· · 题解

前言

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;
}