搜索

KRUMPIRKO 土豆 - llwwll - 博客园


发布时间: 2022-11-24 18:36:01    浏览次数:35 次

[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;
 } 
免责声明 KRUMPIRKO 土豆 - llwwll - 博客园,资源类别:文本, 浏览次数:35 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:36:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/llwwll/p/16810072.html