首页 > 代码库 > UVa 11400 Lighting System Design
UVa 11400 Lighting System Design
题意：
一共有n种灯泡，不同种类的灯泡必须用不同种电源，但同一种灯泡可以用同一种电源。每种灯泡有四个参数：
电压值V、电源费用K、每个灯泡的费用C、所需该种灯泡的数量L
为了省钱，可以用电压高的灯泡来代替电压低的灯泡。输出最小费用。
分析：
每种电源的灯泡要么不换要么全换，因为只换部分的话，两种类型的电源都要买，不划算。
将电压从小到大排序，s[i]表示前i种灯泡一共需要多少个灯泡，d[i]表示前i种灯泡最少费用。
d[i] = min{d[j] + (s[i] - s[j]) * c[i] + k[i]} (j = 0,,,i-1) (表示前j种灯泡用最优解，第j+1~i 种都被第 i 种灯泡所替换而且用第i种电源)
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1000 + 10; 9 struct Lamp10 {11 int v, k, c, l;12 bool operator< (const Lamp& a) const13 {14 return v < a.v;15 }16 }lamps[maxn];17 int s[maxn], d[maxn];18 19 int main(void)20 {21 #ifdef LOCAL22 freopen("11400in.txt", "r", stdin);23 #endif24 25 int n;26 while(scanf("%d", &n) == 1 && n)27 {28 for(int i = 1; i <= n; ++i)29 scanf("%d%d%d%d", &lamps[i].v, &lamps[i].k, &lamps[i].c, &lamps[i].l);30 sort(lamps + 1, lamps + 1 + n);31 s[0] = 0;32 for(int i = 1; i <= n; ++i) s[i] = s[i-1] + lamps[i].l;33 34 d[0] = 0;35 for(int i = 1; i <= n; ++i)36 {37 d[i] = d[i-1] + lamps[i].c * lamps[i].l + lamps[i].k; //用第i种灯泡和电源38 for(int j = 0; j < i; ++j)39 {//前j种灯泡用最优解，第j+1~i 种都被第 i 种灯泡所替换而且用第i种电源40 d[i] = min(d[i], d[j] + (s[i] - s[j]) * lamps[i].c + lamps[i].k);41 }42 }43 printf("%d\n", d[n]);44 }45 46 return 0;47 }
UVa 11400 Lighting System Design
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。