P1417 烹调方案 题解&贪心杂谈

Description

一共有 $n$ 个食物，每个食物有3个属性，分别为 $a,b,c$，其中 $c$ 表示做这道菜的耗时。

一个食物的贡献为 $a-b\times t$，其中 $t$ 表示做完这道菜的总耗时，求在 $T$ 个单位时间内，最多能产生多少贡献。

Solution

首先，通过 $T$ 的限制，$a-b\times t$ 的贡献可以看出这是一道背包问题。

我们考虑 $f_{i,j}$ 表示前 $i$ 个食物耗时 $j$ 的时间所得贡献的最大值，而裸的背包是不用排序的，所以考虑直接DP。

很快就能发现，这个做法假掉了，因为遍历到 $y$ 的时候选了 $x,y$，而到 $z$ 的时候，最佳方案却为 $y,z$，具有后效性。举个例子：

• $a_1=15,a_2=16,a_3=15$
• $b_1=2,b_2=3,b_3=2$
• $c_1=4,c_2=3,c_3=3$

在7个单位时间内，若按输入顺序遍历，得到的最大贡献为8（先做第一道菜，再做第三道），而实际上，最大贡献为10（先做第二道菜，再做第三道菜）。

所以我们尝试用贪心寻找一个正确的排序方案。

我们发现，这道题和一道小学奥数题有些类似，即排队打饭或排队接水问题：

有 $n$ 个人，每个人耗费 $a_i$ 秒打饭，请问应怎么排序，能使每个人的排队时间总和最短。

这道题很简单，按照打饭时间从小到大排序即可。

回到本题，我们是否也能按 $c_i$ 从小到大排序呢。

答案是不行。

因为一个食物的贡献只中 $b_i$ 也是和排序顺序相关的，只有 $a_i$ 是与排序无关的。

所以我们考虑列出式子，找到真正的排序方案。

钦定 $i,j$ 的排序是优于 $j,i$ 的，那么：

$a_i-b_i\times (t+c_i)+a_j-b_j\times (t+c_i+c_j)>a_j-b_j\times (t+c_j)+a_i-b_i\times (t+c_j+c_i)$

拆开括号，化简得：$b_j\times c_i<b_i\times c_j$

到这里，我们的比较器已经出来了，很多同学到这里就会直接开始码字，然后发现是正确的，但为什么这是正确的呢。

正确性证明在许多题解中都是一笔略过的，但有大神说过，一道题如果没有严谨的正确性证明，那么这道题的价值就几乎没有，这句话是有理的。

我们上面的证明只证明了 $i,j$ 在这个比较器下是优于 $j,i$ 的，但没有证明当 $i,j$ 更优，$j,k$ 更优时，$i,k$ 也是更优的，也就是说，只有一个比较器能在有限次数内将一个无序的数列转化为最有的排列，才能证明这个比较器是正确的。

将上述转为数学式子：

已知 $\{\begin{array}{l}{b}_j\times c_i<b_i\times c_j\\ b_k\times c_j<b_j\times c_k\end{array}$

求证 $b_k\times c_i<b_i\times c_k$

证明如下：

由一式与二式可得 $b_j\times c_i+b_k\times c_j<b_i\times c_j+b_j\times c_k$

$\therefore b_j\times (c_i-c_k)<c_j\times (b_i-b_k)$

$\therefore \frac{b_j}{c_j}<\frac{b_i-b_k}{c_i-c_k}$

将二式转换可得 $\frac{b_k}{c_k}<\frac{b_j}{c_j}$

$\therefore \frac{b_k}{c_k}<\frac{b_i-b_k}{c_i-c_k}$

$\therefore b_k\times (c_i-c_k)<c_k\times (b_i-b_k)$

拆开后合并同类项，$b_k\times (c_i+c_k)<c_k\times (b_i+b_k)$

$\therefore \frac{c_i+c_k}{c_k}<\frac{b_i+b_k}{b_k}$

$\therefore \frac{c_i}{c_k}+1<\frac{b_i}{b_k}+1$

$\therefore b_k\times c_i<b_i\times c_k$

证毕。

比较器证明完后，我们回到DP上，发现DP的转移顺序也十分重要。

在转移 $t$ 时，我们要从大到小地遍历。

因为 $t$ 较大的方案是通过 $t$ 较小的方案转移而得，所以如果从小到大遍历，$t$ 较小的方案可能会被更新，导致 $t$ 较大的方案出现错误。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n;
long long dp[100010];  //注意数据范围，要开long long
struct food{
	long long a,b,c;
}s[100];
bool cmp(food x,food y){
	return x.c*(-y.b)>y.c*(-x.b);
}
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].a;
	}
	for(int i=1;i<=n;i++){
		cin>>s[i].b;
	}
	for(int i=1;i<=n;i++){
		cin>>s[i].c;
	}
	sort(s+1,s+1+n,cmp); 
	for(int i=1;i<=n;i++){
		for(int j=t;j>=s[i].c;j--){  //注意遍历顺序
			dp[j]=max(dp[j],dp[j-s[i].c]+s[i].a-j*s[i].b);
		}
	}
	long long ans=0;
	for(int i=1;i<=t;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
}

绝大多数时候，贪心都是口胡而得，并无严谨证明，而很多时候贪心也是因此假掉的。虽然贪心很重要，但更重要的是掌握它的正确性证明，以及如何在考场上快速得出正确贪心的策略。