题目链接：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 个先用最优方案，后面的 j+1~i都用第 I 号的电源。
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = + ; 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 = ; i <= n; i++)
cin >> lamp[i].v >> lamp[i].k >> lamp[i].c >> lamp[i].l;
sort(lamp+, lamp+n+);
s[] = ;
for(int i = ; i <= n; i++) s[i] = s[i-] + lamp[i].l;
d[] = ;
for(int i = ; i <= n; i++) {
d[i] = s[i] * lamp[i].c + lamp[i].k; // 前i个灯泡全买类型i
for(int j = ; 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 ;
}