`
java-mans
  • 浏览: 11342029 次
文章分类
社区版块
存档分类
最新评论

【2012百度之星/初赛下】C:度度熊的礼物

 
阅读更多

描述:度度熊拥有一个自己的Baidu空间,度度熊时不时会给空间朋友赠送礼物,以增加度度熊与朋友之间的友谊值。度度熊在偶然的机会下得到了两种超级礼物,于是决定给每位朋友赠送一件超级礼物。不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。开心值衡量标准是这样的:每种超级礼物都拥有两个属性(A, B),每个朋友也有两种属性(X, Y),如果该朋友收到这个超级礼物,则这个朋友得到的开心值为A*X + B*Y。
由于拥有超级礼物的个数限制,度度熊很好奇如何分配这些超级礼物,才能使好友的开心值总和最大呢?

输入

第一行n表示度度熊的好友个数。

接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi, Yi。

接下来2行,每行三个整数ki, Ai, Bi,表示度度熊拥有第i种超级礼物的个数以及两个属性值。

1<=n<=1000, 0<=Xi,Yi, Ai, Bi 1+k2>=n

输出

输出一行一个值表示好友开心值总和的最大值

样例输入

4

3 6

7 4

1 5

2 4

3 3 4

3 4 3

样例输出

118

提示

送给第一种礼物的人有1,3,4,送给第二种礼物的人有2

代码1:
#include<iostream>
#include<algorithm>
using namespace std;
int f[1001];
struct node
{
	int x , y;
}human[1001];
int num1,num2,a1,b1,a2,b2;

int main(void)
{
	int n , i , j , ans;
	scanf("%d",&n);
	for(i = 1 ; i <= n ; ++i)
		scanf("%d %d" , &human[i].x , &human[i].y);
	scanf("%d %d %d" , &num1 , &a1 , &b1);
	scanf("%d %d %d" , &num2 , &a2 , &b2);

	memset(f,-1,sizeof(f));
	//printf("%d\n",f[1]);
	ans = -1000000;
	f[0] = 0;
	for(i = 1 ; i <= min(n,num2) ; ++i)
		f[i] = f[i-1] + human[i].x*a2 + human[i].y*b2;
	if(f[n] > ans)
		ans = f[n];
	//f[0]=human[1].a*a1+human[1].b*b1;
	//printf("ans:%d\n",ans);
	for(i = 1 ; i <= min(num1,n) ; ++i)
	{
		f[0] = f[0] + human[i].x*a1 + human[i].y*b1;
		//printf("i:%d j:0 f:%d\n",i,f[0]);
		for(j = 1 ; j <= min(n-i,num2) ; ++j)
		{
			f[j] = max(f[j-1]+human[i+j].x*a2+human[i+j].y*b2 , f[j]+human[i+j].x*a1+human[i+j].y*b1);
			//printf("i:%d j:%d f:%d\n",i,j,f[j]);
		}
		if(f[n-i] > ans)
			ans = f[n-i];
	}
	printf("%d\n",ans);
	return 0;
}

代码2:

#include<iostream>
using namespace std;

int c[1000][2000];

int maxx(int a,int b)
{
    if(a > b)
        return a;
	else
		return b;
}

int main(void)
{
    int i , j , t , n , k1 , k2 , a1 , a2 , b1 , b2 , max;
    int x[1001] , y[1001];
    cin >> n;
    for (i = 1 ; i <= n ; ++i)
        cin >> x[i] >> y[i];
    cin >> k1 >> a1 >> b1 >> k2 >> a2 >> b2;

	t = maxx(x[1]*a1+y[1]*b1,x[1]*a2+y[1]*b2);
    c[1][k1+k2] = x[1]*a1+y[1]*b1;
    c[1][0] = x[1]*a2+y[1]*b2;
    for(i = 1 ; i <= k1+k2-1 ; ++i)
        c[1][i] = t;
    for(j = 2 ; j <= n ; ++j)
    {
        for(i = 0 ; i <= k1+k2-j+1 ; ++i)
            c[j][i] = maxx(c[j-1][i+1]+x[j]*a1+y[j]*b1,c[j-1][i]+x[j]*a2+y[j]*b2);
    }
	max = 0;
    for(i = 0 ; i <= k1+k2-n+1 ; ++i)
    {
        if(c[n][i] > max)
            max = c[n][i];
    }
    cout << max << endl;
    return 0;
}
DP方法:
#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1002; 
int x[MAXN], y[MAXN], dp[MAXN][MAXN], a[3], b[3], k[3]; 

int main(void)
{
	int n , i , j , ans , c1 ,c2;
	while(scanf("%d", &n) != EOF)
	{
		for (i = 1; i <= n; ++i)
		{
			scanf("%d %d", &x[i], &y[i]);
		}
		for (i = 1; i <= 2; ++i)
		{
			scanf("%d %d %d", &k[i], &a[i], &b[i]);
		}
		memset(dp , 0 , sizeof(dp));
		for (i = 1; i <= n; ++i)
		{
			for (j = 0; j <= k[1] && j <= i; ++j)
			{
				if (i - j > k[2])
					continue;
				c1 = a[1] * x[i] + b[1] * y[i] ;
				c2 = a[2] * x[i] + b[2] * y[i] ;
				if(j)
					dp[i][j] = dp[i - 1][j - 1] + c1;
				if(i - j)
					dp[i][j] = max(dp[i][j], dp[i - 1][j] + c2);
			}
		}
		ans = 0;
		for (i = 0; i <= k[1]; ++i)
			ans = max(ans, dp[n][i]);
		printf("%d\n", ans);
	}
	return 0;
}


分享到:
评论

相关推荐

    三菱PLC例程源码QD75P八轴定位系统程序

    三菱PLC例程源码QD75P八轴定位系统程序本资源系百度网盘分享地址

    WeRoBot-0.3.2-py2.7.egg

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_serving_api_gpu-1.14.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码ro1-chunshui

    三菱PLC例程源码ro1_chun shui本资源系百度网盘分享地址

    产品经理与产品原型(详解)

    互联网产品经理在向技术部门递交产品策划方案时,除了详尽的需求阐述,一份清晰易懂的产品原型设计方案同样不可或缺。一份出色的原型设计,不仅能促进前期的深入讨论,更能让美工和开发人员更直观地理解产品特性,进而优化工作流程,减少不必要的时间消耗,提升整体工作效率。接下来,我想就产品经理与原型设计之间的关系进行简要的探讨,并期待能与大家进行深入的交流和探讨。 产品原型,简而言之,是产品设计最终成形之前的一个基础框架。对于网站而言,它意味着对页面模块和元素进行初步、大致的排版与布局。进一步讲,我们还会加入一些交互性元素,使原型更加具体、生动,更贴近最终产品的形态,从而帮助团队成员更好地理解和构建产品。 很多人存在一个误区,认为UI、UE设计师的职责就是将产品原型转化为具体的页面效果。然而,实际上他们的工作流程是在原型设计完成之后展开的。在整个产品开发流程中,产品经理是最了解产品特性、用户和市场需求的角色。尽管设计师在视觉设计方面可能表现得非常出色,但他们在理解产品、用户、市场及业务方面的深度与准确性上,往往无法与产品经理相提并论。准确地说,设计师的工作是将产品原型转化为产品经理所期望的视觉效果。

    小红书娱乐营销520明星大事件《全明星告白季》招商方案ss.pptx

    小红书娱乐营销520明星大事件《全明星告白季》招商方案ss.pptx

    本科毕业设计-基于深度学习的模糊人脸图像增强系统的设计与实现.zip

    人工智能毕业设计&课程设计

    三菱PLC例程源码车辆进出车库

    三菱PLC例程源码车辆进出车库本资源系百度网盘分享地址

    三菱PLC例程源码PLCFX0N三层三站程序

    三菱PLC例程源码PLCFX0N三层三站程序本资源系百度网盘分享地址

    三菱PLC例程源码纯水控制三菱PLC实例和触摸屏程序

    三菱PLC例程源码纯水控制三菱PLC实例和触摸屏程序本资源系百度网盘分享地址

    三菱PLC例程源码pp復卷機三菱伺服編程

    三菱PLC例程源码pp復卷機三菱伺服編程本资源系百度网盘分享地址

    三菱PLC例程源码变频器16段速控制

    三菱PLC例程源码变频器16段速控制本资源系百度网盘分享地址

    wheel-0.34.2.tar.gz

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于SSM框架的二手物品交易管理系统设计源码

    这是一个基于SSM框架的二手物品交易管理系统设计,使用Java语言开发,包含344个文件。主要文件类型包括59个JPG图片文件、59个Java源文件、48个PNG图片文件、37个JAR包文件、34个JavaScript文件、28个JSP文件、26个CSS文件、16个XML文件和5个GIF图片文件。该项目提供了一个全面的二手物品交易平台,支持用户发布商品、查看闲置、充值账户、查看所有订单和发布求购信息,旨在为用户提供便捷、安全的交易环境。

    tensorflow_privacy-0.2.1-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    使用DS Client在PPT中动态展示分子三维结构.pdf

    使用DS Client在PPT中动态展示分子三维结构

    quartus ii安装教程.docx

    quartus ii安装教程

    基于ssm高校食堂订餐系统.zip

    基于ssm高校食堂订餐系统.zip

    Google-JavaScript-编码规范指南

    Google JavaScript编码规范指南是Google公司推出的一套详尽且实用的JavaScript编程规范,旨在为开发者提供一个清晰、一致的编码标准,以提高代码质量、可读性和可维护性。这套规范不仅涵盖了JavaScript语言的基础语法和常见模式,还针对Google的实际项目需求,提供了一系列最佳实践和建议。 通过遵循Google JavaScript编码规范指南,开发者可以确保自己的代码风格与团队其他成员保持一致,减少因编码习惯不同而引发的沟通成本和潜在错误。规范中详细说明了变量命名、函数定义、注释书写、代码格式化等方面的要求,使得代码更加整洁、易于阅读和理解。 此外,Google JavaScript编码规范指南还强调了代码性能和可维护性的重要性。它提倡使用高效的数据结构和算法,避免不必要的性能开销;同时,也鼓励开发者编写可重用的代码,减少重复劳动,提高开发效率。 对于初学者来说,Google JavaScript编码规范指南也是一本极佳的入门教材。它可以帮助初学者养成良好的编程习惯,掌握JavaScript的核心概念和技巧,为未来的项目开发打下坚实的基础。

    tensorflow_ranking-0.5.3-py2.py3-none-any.whl

    算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

Global site tag (gtag.js) - Google Analytics