设计照明系统
2019-07-14 00:19发布
生成海报
试题描述
设计一个照明系统。共有n种灯泡供你选择,不同种类的灯泡必须使用不同种类的电源,但同一种灯泡可以共用一个电源。所有灯泡的电流参数相同,电压不同。现在给你每种灯泡的四个参数:电压V,电源费用K,每个灯泡的价格C,以及需要该种灯泡的数量L。为了减少费用,你可以把电压低的灯泡换成电压更高的灯泡,而省出电源的费用(某种灯泡全换成别的种类,就可以共用别的电源,从而少配一个电源,不就节约了一个电源的费用吗?)。请你配置方案,使系统造价最小。新的方案标准不能降低,灯泡的数量不能减少,电流相同、电压高的灯泡功率也更大,也会更亮。
输入
第一行包括一个正整数n,接下来的n行,每行描述一种灯泡的参数,分别为V,K,C和L。两数之间用一个空格分隔。
输出
一个数表示电源的最小费用。
输入示例
3 12 300 10 30 18 400 15 28 30 500 13 30
输出示例
1644
其他说明
数据范围:0 < n <= 1000,0 < V <= 132000,0 < K <= 1000,0 < C <= 20,0 < L <= 100
#include
using namespace std;
int n;
int s[10010],dp[10010];
struct node//定义结构体详情请见1、
{
int v,k,c,l;
bool operator < (const node & a)const//详情请见重载运算符2、
{
return v<a.v;
}
}
a[1005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)//输入结构体
cin>>a[i].v>>a[i].k>>a[i].c>>a[i].l;
sort(a+1,a+n+1);//这一定要在有运算符重载下才能排序结构体
for(int i=1;i<=n;i++)//这就是经典的前缀和
s[i]=s[i-1]+a[i].l;
memset(dp,27,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j)
dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*a[i].c+a[i].k);//核心代码
cout<<dp[n];
}
/*
1、结构体:一个新的数据类型,名字由自己定义,地位与用法和int相同
语法规则:
struct(类型名)
{
变量列表(可以附加函数)
}
例如:
struct student
{
int chinese;
int math;
int english;
}
student stu[10010];
使用时:stu[1].chinese(第一个学生的语文成绩)
2、memset(dp,27,sizeof(dp))(给dp数组每一个变量赋予最大值)
3、重载运算符:这当模板背就行了。
bool operator < (const node & a)const
{
return v*/
View Code
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮