自动搬运

查看原文

来自洛谷，原作者为

	ybe2007 适度OI益脑，沉迷OI伤身

搬运于2025-08-24 22:33:13，当前版本为作者最后更新于2022-07-12 09:55:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一开始拿到题，除了爆搜肯定是没有什么思路的。于是我们考虑先推一下式子，看看能否通过适当的转化用高效的算法求解。

题目要求 ${(P_1 \times P_2)}_{\min}$，那么我们考虑将结果用另一种表现形式呈现。

$P_1 \times P_2= \dfrac{x}{y} \times \dfrac{\sum{c_i}-x}{\sum{a_i}-y}=\dfrac{x\times \sum{c_i}-x^2}{y\times \sum{a_i}-y^2}$，其中 $x$ 表示选取的土豆总价值，$y$ 表示选取的土豆总个数（对于一家店而言）。

观察到 $n,\sum{a_i}$ 均较小，那么考虑动态规划，开一个三维的 $\text{dp}$ 数组 $f_{i,j,k}$ 表示前 $i$ 袋土豆，选择 $j$ 袋，选取土豆总个数为 $k$ 时的情况。题目要求最小值，但是发现转移过程中似乎直接记录 ${(x\times sumc-x^2)}_{\min}$ 是不可行的。

但是观察到这个式子是一个二次函数的表达式，二次项系数为负，开口朝下，那么对于这样一个单峰函数很显然其最小值在 $x$ 取极值时取到，因此我们开 $f,g$ 两个数组，记录 $x$ 的最小值和最大值，那么转移方程与最后求解的答案就很明显了。具体可以看看代码。

当然第一维可以用滚动数组压掉，算是一个小优化吧。

答案的计算可能会溢出 $\text{int}$，中间记得强制转化一下。

#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,l;
int f[2][N][505],g[2][N][505];
int a[N],c[N],suma,sumc;
int main()
{
	scanf("%d%d",&n,&l);
	l=min(l,n-l);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),suma+=a[i];
	for(int i=1;i<=n;i++) scanf("%d",&c[i]),sumc+=c[i];
	memset(f,0x3f,sizeof(f)),memset(g,-0x3f,sizeof(g));
	f[0][0][0]=g[0][0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=min(i,l);j++)
		{
			for(int k=0;k<=suma;k++)
			{
				f[i&1][j][k]=f[i-1&1][j][k],g[i&1][j][k]=g[i-1&1][j][k];
				if(k>=a[i]&&j)
				{
					f[i&1][j][k]=min(f[i&1][j][k],f[i-1&1][j-1][k-a[i]]+c[i]);
					g[i&1][j][k]=max(g[i&1][j][k],g[i-1&1][j-1][k-a[i]]+c[i]);
				}
			}
		}
	}
	double ans=1e16;
	for(int i=1;i<=suma;i++)
	{
		if(f[n&1][l][i]<1e9) ans=min(ans,1ll*f[n&1][l][i]*(sumc-f[n&1][l][i])*1.0/(1ll*i*(suma-i)));
		if(g[n&1][l][i]>-1e9) ans=min(ans,1ll*g[n&1][l][i]*(sumc-g[n&1][l][i])*1.0/(1ll*i*(suma-i)));
	}
	printf("%.3lf\n",ans);
}