用DP记录贡献的问题

本文介绍: 中取值，我们找出这些值，从大到小枚举最小值的同时维护最小的最大值即可，得到了一个。时，最大值最小为多少，我们在计算每个位置可能的取值时把它处理出来即可，得到了。最大为多少的怪物，显然它是单调不降的，处理之后在。的解法（常数也很大），但是不足以通过本题。内的所有怪物，于是同样的，我们利用数组。表处理出区间最小值，可以得到一个。的方法，同样不足以通过此题。很容易观察到每个位置有。的解法，可以通过本题。

logn+nlogn)的方法，同样不足以通过此题。

int n,m,k;
int a[N],b[N],tot=0;
int C;
int ST[N][21],lg2[N];
void init_ST(int* num,int n){
	for(int i=1;i&lt;=n;i++)ST[i][0]=num[i];
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r){
	int mid=lg2[r-l+1];
	return min(ST[l][mid],ST[r-(1<<mid)+1][mid]);
}
int find(int s,int x){
	int l=s,r=tot;
	if(b[r]<=x)return r;
	while(l+1<r){
		int mid=l+r&gt;&gt;1;
		if(b[mid]<=x)l=mid;
		else r=mid;
	}
	return l;
}
inline void solve(){
	cin&gt;&gt;n&gt;>C;
	lg2[0]=-1;
	for(int i=1;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	map<int,int>num;
	for(int i=0;i<n;i++){
		int c,d,h;cin>>c>>d>>h;
		if(num.count(d*h))num[d*h]=min(num[d*h],c);
		else num[d*h]=c;
	}
	tot=0;
	for(auto t:num){
		a[++tot]=t.se;
		b[tot]=t.fi;
	}
	init_ST(a,tot);
	
	cin>>m;
	while(m--){
		int D,H;cin>>D>>H;
		int ans=INF,mul=D*H;
		for(int i=find(1,mul/C);i<=tot;i++){
			int t=mul/b[i],vr;
			if(t)vr=mul/t;
			else vr=INF;
			int pr=find(i,vr);
			
			int mn=query(i,pr);
			ans=min(ans,(t+1)*mn);
			i=pr;
		}
		if(ans>C)cout<<-1<<' ';
		else cout<<ans<<' ';
	}
}

正解

我们还观察到，使用

$k$ 个

unit

$u ni t$ 可以击败

≤

∗

−

1leq HDleq k*hd-1

$1 \leq HD \leq k * h d - 1$ 内的所有怪物，于是同样的，我们利用数组

$d p$ 来计算贡献，

[

]

dp[i]

$d p [i]$ 表示花费为

$i$ 时，可以打败

$HD$ 最大为多少的怪物，显然它是单调不降的，处理之后在

$d p$ 数组上二分即可，复杂度为

(

)

O((n+m)logC)

$O ((n + m) l o g C)$ 。

int n,m,k;
int dp[N];
int C;
inline void solve(){
	cin>>n>>C;
	map<int,int>num;
	for(int i=0;i<n;i++){
		int c,d,h;cin>>c>>d>>h;
		if(num.count(c))num[c]=max(num[c],d*h);
		else num[c]=d*h;
	}
	for(auto t:num){
		for(int j=t.fi;j<=C;j+=t.fi){
			int cnt=j/t.fi;
			dp[j]=max(dp[j],cnt*num[t.fi]-1);
		}
	}
	
	for(int i=1;i<=C;i++)dp[i]=max(dp[i],dp[i-1]);
	
	cin>>m;
	while(m--){
		int H,D;cin>>H>>D;
		int l=0,r=C;
		if(dp[r]<H*D){
			cout<<-1<<' ';
			continue;
		}
		while(l+1<r){
			int mid=l+r>>1;
			if(dp[mid]<H*D)l=mid;
			else r=mid;
		}
		cout<<r<<' ';
	}
}