Lighting System Design UVA - 11400（dp）

ゞ浴缸里的玫瑰 2022-05-20 10:34 129阅读 0赞

思路：根据题意，只能用等级大的替换等级小的，所以先将灯排序，接下来就是如何替换的问题， 可以证明 替换一定是连续的替换，假如说有 a, b, c， d三个灯， 替换非连续替换，就是说d替换了a， c，没有替换b， 这也就是说b的花费是足够小，无法让d替换，那么b一定可以替换a，也就是说b替换了a， d替换了c；

所以转移方程为 dp\[i\]=min(dp\[i\],  dp\[j\]+lamp\[i\].c\*(s\[i\]-s\[j\])+lamp\[i\].k) //dp\[i\]代表前i个灯替换的最小花费。

#include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    typedef long long ll;
    
    struct node{
        ll v, k, c, l;
    }lamp[N];
    
    ll dp[N], s[N];
    
    bool cmp(node a, node b){
        return a.v<b.v;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d", &n)&&n){
            for(int i=1; i<=n; i++){
                scanf("%lld%lld%lld%lld", &lamp[i].v, &lamp[i].k, &lamp[i].c, &lamp[i].l);
            }
    
            sort(lamp+1, lamp+1+n, cmp);
            memset(dp, 0x3f, sizeof(dp));
            memset(s, 0, sizeof s);
            dp[0]=0;
            for(int i=1; i<=n; i++){
                s[i]=s[i-1]+lamp[i].l;
                for(int j=i-1; j>=0; j--){
                    dp[i]=min(dp[i], dp[j]+lamp[i].k+lamp[i].c*(s[i]-s[j]));
                }
            }
    
            printf("%lld\n", dp[n]);
    
    
        }
    
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 uva 10271 Chopsticks 【dp】

题目：uva 10271Chopsticks 题意：从一组数中选出每三个为一组，价值为三个中两个小的差值的平方和，让这个总价值最小。分析：定义dp【i

Myth丶恋晨/ 2022年08月12日 16:19/ 0 赞/ 131 阅读

相关 uva 10110——Light, more light

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

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

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

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

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

相关数位DP UVA - 11038

数位DP，顾名思义，是在个位，十位，百位，千位…….这些数的数位上进行的DP，它其实就是一种暴力枚举+记忆化搜索。数位DP一般用来解决要求找出某个区间内，满足要求的数有多

ゝ一纸荒年。/ 2022年06月09日 00:29/ 0 赞/ 269 阅读

相关 Lighting System Design UVA - 11400（dp）

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

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

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

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

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

相关 DP-UVA 10036-Divisibility

DP-UVA 10036-Divisibility -------------------- 题目链接： [10036 - Divisibility

桃扇骨/ 2022年05月14日 22:22/ 0 赞/ 129 阅读

相关 uva 11400 - Lighting System Design

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

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

相关 UVA 10003 区间DP

题意：有一根长度为l的木棍，木棍上面有m个切割点，每一次切割都要付出当前木棍长度的代价，问怎样切割有最小代价。分析：石子合并的逆过程。状态：设F（i，j）为区间(

绝地灬酷狼/ 2021年12月18日 15:19/ 0 赞/ 252 阅读

相关 uva10859 (树形dp)

题意：给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量

青旅半醒/ 2021年12月14日 03:21/ 0 赞/ 338 阅读