DP不能干的事情，我贪心+特判干掉了！

前言

说来话长，那天我们拿到这张《杂题选讲》，指着看起来非常easy的T2讨论起来。

XXX：一看就是个背包变式。

XXX：肯定是贪心。

XX：确实像个背包，但物品少貌似能贪心？

然后放学回家，LQ上网搜素一波：哇！atcoder水题！水它！

题意

单子上写得明明白白

算了还是当回搬运工

初始化 \(P=0\)，给定 \(N,A,B,X,Y,Z\)，可以执行三种操作任意次：

• 花费 \(X\) 元将 \(P+1\)；

• 花费 \(Y\) 元将 \(P+A\)；

• 花费 \(Z\) 元将 \(P+B\)。

求 \(P=N\) 的最小花费。

\(1 \le N,A,B,X,Y,Z \le 10^9\)

注意：有多组数据。

思路

看到范围果断干掉DP，考虑一下基于性价比的贪心思想。

首先发现，操作1可以用于填充另两个操作不能填满的部分。

同时可以进行一些特判：

• 若操作1的性价比比其他都高，则用操作1填满；

• 若操作1的性价比高于一项而低于另一项，不妨设高于操作2，低于操作3，则可以填充完操作2后用操作1补全。

完成特判后，我们只需要着手于一种情况：操作1的性价比最劣，即不能不用时才能用。

那么现在面临的问题就是：合理选择操作2与操作3的次数，使费用最少。

不妨暴力一点，直接枚举。真够bf的。

现在操作2的上限次数为 \(\lfloor \frac{N}{A} \rfloor\)，操作3的上限次数为 \(\lfloor \frac{N}{B} \rfloor\)，无论选择哪项进行枚举，都可以卡到单次 \(O(N)\)，显然不能承受。

考虑死不悔改。如果我们默认操作2的性价比更优，则可以发现操作3的上限次数会被限制在 \(A-1\)，即 \(N \bmod A\) 的级别：若超出这个限制的操作，一定能被性价比更优的操作2所取代。

此时选择级别较小的一项枚举，就不会超时了，单次时间复杂度为 \(O(\sqrt N)\)。

为啥呢？

因为官方题解也是这么干的

好吧，我们来试着卡一下这个做法：

1. 卡 \(\lfloor \frac{N}{A} \rfloor\) ，此时我们要卡他，需要把 \(A\) 干到 \(1\)，那么 \(A-1\) 就跑得飞快。

2. 卡 \(A-1\)，此时需要把 \(A\) 整到 \(N\)，那么 \(\lfloor \frac{N}{A} \rfloor\) 就卡不动了。

3. 于是为了一个平衡，我们把 \(A\) 设为 \(\sqrt N\)，那么两边都没法卡，而测试数据的数量在 \(100\) 以内，根本卡不动。

综上，我们就得到了这个好写又快的做法。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x7fffffffffffffff;
int N;
ll A,B,X,Y,Z;
inline ll solve(){
	if(Y*B>Z*A) swap(Y,Z),swap(A,B);
	int a=N/A,b=A-1;
	if(X*A<=Y) return N*X;
	if(X*B<=Z) return a*Y+N%A*X;
	ll ret=INF;
	if(a<=b){
		for(int i=0;i<=a;i++){
			int n=N-i*A;
			ret=min(ret,i*Y+n/B*Z+n%B*X);
		}
	}
	else{
		for(int i=0;i<=b;i++){
			int n=N-i*B;
			if(n>=0) ret=min(ret,i*Z+n/A*Y+n%A*X);
		}
	}
	return ret;
}
signed main(){
	int T=0;
	scanf("%d",&T);
	for(;T--;){
		scanf("%d%lld%lld%lld%lld%lld",&N,&A,&B,&X,&Y,&Z);
		printf("%lld\n",solve());
	}
	return 0;
}

对了兄弟们，我不卡常了！