题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=2395

题意：你的任务是设计一个照明系统。一共有n(n≤1000)种灯泡可供选择，不同种类的灯泡必须使用不同的电源，但同一种灯泡可以共用一个电源。每种灯泡用4个数值表示：电压值V(V≤132000)，电源费用K(K≤1000)，每个灯泡的费用C(C≤10)和所需灯泡的数量L(1≤L≤100)。假定通过所有灯泡的电流都相同，因此电压高的灯泡功率也更大。为了省钱，可以把一些灯泡换成电压更高的另一种灯泡以节省电源的钱（但不能换成电压更低的灯泡）。你的任务是计算出最优方案的费用。（本段摘自《算法竞赛入门经典（第2版）》）

分析：
对于一种灯泡而言，要么全部换掉要么全部不换。先把灯泡按照电压从小到大排序，设s[i]为前i种灯泡的总数量，dp[i]为灯泡1~i的最小开销，则dp[i]=min(dp[j]+(s[i]−s[j])∗c[i]+k[i])，表示前j个先用最优方案买，然后j+1~i个都用第i号电源。最终答案为dp[n]。 代码： #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 1000 + 5, INF = 1e9; struct Node { int v, k, c, l; bool operator < (const Node& right) const { return v < right.v; } }; int n, tmp; int dp[maxn], s[maxn]; Node a[maxn]; int main() { while (~scanf("%d", &n), n) { for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &a[i].v, &a[i].k, &a[i].c, &a[i].l); sort(a + 1, a + n + 1); for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] + a[i].l; tmp = INF; for (int j = 0; j < i; ++j) tmp = min(tmp, dp[j] + (s[i] - s[j]) * a[i].c + a[i].k); dp[i] = tmp; } printf("%d ", dp[n]); } return 0; }