uva 11400 - Lighting System Design

一时失言乱红尘 2021-12-19 02:55 166阅读 0赞

## 题意：给出n个模式，每个模式有电压v，电压费用k，每盏灯的花费c以及灯数l。然后电压高的可以用于电压低的。问说最少花费多少钱可以满足n个模式。 ##

## 分析：每种电压的灯泡要么全换，要么都不换，不然两种电源都不要。因为低电压灯泡可以用较高的电源。按电压从低到高排一遍。设s\[i\] 前 i 种灯泡的总数量， d\[i\] 为灯泡1~i的最小开销，d\[i\] = min(d\[j\]+(s\[i\]-s\[j\])\*c\[i\]+k\[i\])，前 j 个先用最优方案，后面的 j+1~i都用第 I 号的电源。 ##

## 代码： ##

#include<iostream>
    #include<algorithm>
    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(lamp+1, lamp+n+1);
            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个灯泡全买类型i
                for(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;
    }

##      ##

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关 Fluent Design System 设计语言元素

Fluent Design System 设计语言共有元素，分别为光照（Light）、深度（Depth）、运动（Motion）、材质（Material）和缩放（Scale），目

客官°小女子只卖身不卖艺/ 2023年07月17日 12:44/ 0 赞/ 1 阅读

相关 Design Underground System（C++设计地铁系统）

解题思路：（1）拼接起点和终点的车站名，保存其行程和出现的次数（2）保存行人id和进站的时间以及车站名 class UndergroundSystem {

左手的ㄟ右手/ 2023年01月05日 12:45/ 0 赞/ 174 阅读

相关 uva 10110——Light, more light

题意：当时还挺绕人，讲的就是一个走廊里有n个灯，一个人（疯了）来回在走廊里转，走第i 圈的时候将灯数能够整除i的灯号改变一下开关，问最后的时候（走n圈的）最后一个灯是明还是暗？

╰+攻爆jí腚メ/ 2022年08月09日 13:48/ 0 赞/ 150 阅读

相关 Your System Is Legacy; Design for It

Your System Is Legacy; Design for It Dave Anderson EvEn iF youR SySTEM iS BlEEdin

绝地灬酷狼/ 2022年08月04日 13:51/ 0 赞/ 157 阅读

相关 ACM DP Lighting System Design&&Jin Ge Jin Qu hao

滴，集训第十五天打卡。哎呀..回家了一趟落下了一大截啊...容我慢慢补起来~~ 训练也到了第九章，dp。 uva 11400 Lighting System Desig

快来打我*/ 2022年06月11日 08:00/ 0 赞/ 94 阅读

相关 Lighting System Design UVA - 11400（dp）

思路：根据题意，只能用等级大的替换等级小的，所以先将灯排序，接下来就是如何替换的问题，可以证明替换一定是连续的替换，假如说有 a, b, c， d三个灯，替换非连续替换，

ゞ浴缸里的玫瑰/ 2022年05月20日 10:34/ 0 赞/ 129 阅读

相关数学题(完全平方数)UVA 10110-Light, more light

数学题(完全平方数)UVA 10110-Light, more light -------------------- 题目链接：[10110 - Ligh

谁借莪１个温暖的怀抱￠/ 2022年05月16日 09:14/ 0 赞/ 144 阅读

相关 uva 11400 - Lighting System Design

题意：给出n个模式，每个模式有电压v，电压费用k，每盏灯的花费c以及灯数l。然后电压高的可以用于电压低的。问说最少花费多少钱可以满足n个模式。分析：每种电压的灯泡要么

一时失言乱红尘/ 2021年12月19日 02:55/ 0 赞/ 167 阅读

相关 System Design of Tiny Url

Why do we need URL shortening For example, if we shorten this page through TinyURL: >

朱雀/ 2021年11月09日 14:02/ 0 赞/ 277 阅读

相关 DGUT-Cnam Courses: Computer System Design & Analysis – Java Programming

DGUT-Cnam Courses: Computer System Design & Analysis – Java Programming Computer Sy

你的名字/ 2021年10月19日 20:38/ 0 赞/ 200 阅读