首页 > 代码库 > UVa 11400 照明系统设计
UVa 11400 照明系统设计
https://vjudge.net/problem/UVA-11400
题意:
有一个照明系统需要用到n种灯,每种灯的电压为V,电源费用K,每个灯泡费用为C,需要该灯的数量为L。注意到,电压相同的灯泡只需要共享一个对应的电源即可,还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本,你将设计一种系统,使之最便宜。
思路:
这道题和我之前做的POJ 1260(具体也可以看一下这题) 基本上是一样的,首先是按电压排序,设sum[i]为前i种灯泡的总数量,d[i]为灯泡1~i的最小开销,则d[i]=min{d[j]+(sum[i]-sum[j])*c[i]+k[i])},表示前j个先用最优方案买,然后第j+1~i个都用第i号的电源。答案为d[n]。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 1000 + 10; 7 8 int n; 9 int d[maxn];10 int sum[maxn];11 12 struct node13 {14 int v, k, c, l;15 }a[maxn];16 17 bool cmp(node a, node b)18 {19 return a.v < b.v;20 }21 22 23 int main()24 {25 //freopen("D:\\txt.txt", "r", stdin);26 while (cin >> n && n)27 {28 29 for (int i = 1; i <= n; i++) 30 {31 cin >> a[i].v >> a[i].k >> a[i].c >> a[i].l;32 }33 sort(a + 1, a + n + 1, cmp); 34 35 sum[0] = 0;36 for (int i = 1; i <= n; i++) {37 sum[i] = sum[i - 1] + a[i].l;38 }39 d[0] = 0;40 for (int i = 1; i <= n; i++) {41 d[i] = d[i - 1] + a[i].c*a[i].l + a[i].k; //未优化之前的购买方式42 for (int j = 0; j < i; j++) {43 d[i] = min(d[i], d[j] + (sum[i] - sum[j]) * a[i].c + a[i].k);44 }45 }46 cout << d[n] << endl;47 }48 return 0;49 }
UVa 11400 照明系统设计
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。