网站建设ppt课件,网页设计入门基础,兰州官网seo技巧,wordpress 主题 百科题目链接#xff1a;https://uva.onlinejudge.org/external/114/11400.pdf 题意#xff1a;有一个照明系统需要用到n种灯#xff0c;每种灯的电压为V#xff0c;电源费用K#xff0c;每个灯泡费用为C#xff0c;需要该灯的数量为L。注意到#xff0c;电压相同的灯泡只需…题目链接https://uva.onlinejudge.org/external/114/11400.pdf 题意有一个照明系统需要用到n种灯每种灯的电压为V电源费用K每个灯泡费用为C需要该灯的数量为L。注意到电压相同的灯泡只需要共享一个对应的电源即可还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本你将设计一种系统使之最便宜。 分析每种电压的灯泡要么全换要么都不换不然两种电源都不要。因为低电压灯泡可以用较高的电源。按电压从低到高排一遍。 设s[i] 前 i 种灯泡的总数量 d[i] 为灯泡1~i的最小开销d[i] min(d[j](s[i]-s[j])*c[i]k[i])前 j 个先用最优方案后面的 j1~i都用第 I 号的电源。 #includeiostream
#includealgorithm
using namespace std;const int maxn 1000 5;struct Lamp {int v, k, c, l;bool operator (const Lamp rhs) const {return v rhs.v;}
} lamp[maxn];int n, s[maxn], d[maxn];int main() {while(cin n n) {for(int i 1; i n; i)cin lamp[i].v lamp[i].k lamp[i].c lamp[i].l;sort(lamp1, lampn1);s[0] 0;for(int i 1; i n; i) s[i] s[i-1] lamp[i].l;d[0] 0;for(int i 1; i n; i) {d[i] s[i] * lamp[i].c lamp[i].k; // 前i个灯泡全买类型ifor(int j 1; j i; j)d[i] min(d[i], d[j] (s[i] - s[j]) * lamp[i].c lamp[i].k);}cout d[n] \n;}return 0;
} 转载于:https://www.cnblogs.com/TreeDream/p/5991014.html
