UVa 11400 - Lighting System Design（白书，比较好）

UVa 11400 - Lighting System Design（白书，比较好）

题目地址：= min(dp[i],dp[j]+sum * a[i].c + a[i].k);dp[i]为前i个灯泡的最下值，其中sum为j+1到i的总数量

AC代码：

#include #include #include #include #include #include #include

作者的标称（用了前缀和，大致思想差不多，每次的初始值不一样）

// UVa11400 Lighting System Design// Rujia Liu#include#includeusing 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。