首页 > 代码库 > UVa 11400 照明系统设计

UVa 11400 照明系统设计

2024-09-02 20:41:55   208人阅读

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 照明系统设计


联系
我们