[COCI2015-2016#6] KRUMPIRKO
ybe2007
·
·
题解
一开始拿到题，除了爆搜肯定是没有什么思路的。于是我们考虑先推一下式子，看看能否通过适当的转化用高效的算法求解。
题目要求 {(P_1 \times P_2)}_{\min}，那么我们考虑将结果用另一种表现形式呈现。
观察到 $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}$，中间记得强制转化一下。
```cpp
#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);
}
```