[COCI2015-2016#6] KRUMPIRKO
题目描述
\(\text{Mr. Potato}\) 开了两家新店卖土豆。他买了 \(N\) 袋土豆，其中第 \(i\) 袋价值为 \(c_i\)，袋里有 \(a_i\) 个土豆。他打算把这 \(N\) 袋土豆整袋整袋地分在两个店里。
在每家店中，土豆的平均价格等于这家店里所有袋的土豆的总价比上土豆的个数。（注意是个数而不是袋数！）
设 \(P_1\) 为第一家店的土豆平均价格，\(P_2\) 为第二家店的土豆平均价格。\(\text{Mr. Potato}\) 希望在至少有一家店里土豆袋数正好等于 \(L\) 袋的情况下，最小化 \(P_1\times P_2\) 的值。
输入格式
第一行包含两个整数 \(N\) 和 \(L\)。
第二行包含 \(N\) 个整数 \(a_i\)。
第三行包含 \(N\) 个整数 \(c_i\)。
输出格式
第一行输出一个浮点数，为 \(P_1\times P_2\) 的最小值，保留到小数点后三位。
样例 #1
样例输入 #1
3 1
3 2 1
1 2 3
样例输出 #1
0.556
样例 #2
样例输入 #2
3 2
2 2 2
3 3 3
样例输出 #2
2.250
提示
【数据范围】
对于 \(30\%\) 的数据，\(2\le N\le 20\)。
对于 \(100\%\) 的数据，\(2\le N\le 100\)，\(1\le L< N\)，\(1\le a_i\le 100\)，\(1\le c_i\le 10^6\)，\(\sum\limits_{i=1}^{N} a_i\le 500\)。
【题目来源】
题目译自 COCI 2015-2016 CONTEST #6 T5 KRUMPIRKO。
本题分值按 COCI 原题设置，满分 \(140\)。
分析
前三十分很好想 \(2^n\) 枚举所有情况即可
正解
\(DP\)
题目要求\(P1\times P2=\frac{x}{y}\times\frac{\sum X-x}{\sum Y-y}\)
其中 \(x\) 表示价格，\(y\) 表示个数
将 \(\sum X\) 与 \(\sum Y\) 看做常数 \(k1\ k2\)
\(P1\times P2=\frac{k_1x-x^2}{k_2y-y^2}\)
这东西不好维护，但是他的分子分母很好搞
就是一个二次函数
那我们分开枚举 \(x\) 的同时，计算 分母 不就好了
为什么说枚举 \(x\) 呢
因为 \(x\) 在二次函数上，二次系数为负，开口朝下，最小值取值有两个
因为两个最小值取值，且一个尽可能的大，另一个尽可能小，就维护一个 \(x\) 的最大最小值
定义 \(dp[i][j][k]\) 为前 \(i\) 袋中选了 \(j\) 袋共 \(k\) 个土豆
很容易写出 \(dp[i][j][k]=(dp[i-1][j][k]\ ,\ dp[i-1][j-1][k-a[i]]+c[i])\)
最后答案枚举 \(k\) 即可
\(Ac\ code\)
#include<bits/stdc++.h>
#define N 110
#define int long long
using namespace std;
int n,L,a[N],c[N];
int suma,sumc;
int dp_n[2][N][5*N];
int dp_x[2][N][5*N];
double ans;
template<typename T>void read(T &x)
{
x=0;char c=getchar();T neg=0;
while(!isdigit(c))neg|=!(c^'-'),c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg)x=(~x)+1;
}//快读
template<typename T>void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar((x-x/10*10)^48);
return ;
}//快写
signed main()
{
// freopen("krumpirkokrumpirko2.in","r",stdin);
read(n);read(L);
for(int i=1;i<=n;i++) read(a[i]),suma+=a[i];
for(int i=1;i<=n;i++) read(c[i]),sumc+=c[i];
memset(dp_n,127,sizeof dp_n);
ans=dp_n[0][0][0];
memset(dp_x,-127,sizeof dp_x);
dp_x[0][0][0]=dp_n[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++)
{
dp_n[i&1][j][k]=dp_n[(i-1)&1][j][k];
dp_x[i&1][j][k]=dp_x[(i-1)&1][j][k];
if(k>=a[i]&&j)
{
dp_n[i&1][j][k]=min(dp_n[i&1][j][k],dp_n[(i-1)&1][j-1][k-a[i]]+c[i]);
dp_x[i&1][j][k]=max(dp_x[i&1][j][k],dp_x[(i-1)&1][j-1][k-a[i]]+c[i]);
}
}
}
}
for(int i=0;i<=suma;i++)
{
if(dp_n[n&1][L][i]<1e10) ans=min(ans,dp_n[n&1][L][i]*(sumc-dp_n[n&1][L][i])*1.0/(i*(suma-i)));
if(dp_x[n&1][L][i]>-1e10) ans=min(ans,dp_x[n&1][L][i]*(sumc-dp_x[n&1][L][i])*1.0/(i*(suma-i)));
}
printf("%.3lf\n",ans);
return 0;
}