uva 11400 - Lighting System Design-蒲公英云

uva 11400 - Lighting System Design

题意：给出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;
}