题解：P8179 「EZEC-11」Tyres

很有意思的题。

先考虑

t=0

怎么做，此时对于每个轮胎，其消耗代价是随跑的圈数单调上升的，因此可以直接贪心。将每个轮胎与其要跑的圈数放进堆里维护即可。可以做到

O(m\log n)

。

再考虑

m

和

n

同阶怎么做，令

f_{i,j}

代表考虑到前

i

个轮胎、目前已经跑了

j

圈的最小代价。转移就是一个朴素的背包：

f_{i,j}=\min \Big(f_{i-1,j},f_{i-1,0}+c(i,j),\min \limits_{k=1}^{j}f_{i-1,j-k}+c(i,k)+t \Big)

其中

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)

，可以通过。

CPP

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

题解：P8179 「EZEC-11」Tyres

文章操作

相关推荐

评论

题解：P8179 「EZEC-11」Tyres