題目：題目鏈接

思路：簡單的動態規劃問題，先把燈泡按照電壓從小到大排序。設s[i]為前i種燈泡的總數量（即L值之和），d[i]為燈 泡1～i的最小開銷，則d[i] = min{d[j] ＋ (s[i]－s[j])*c[i] ＋ k[i])}，表示前j個先用最優方案 買，然后第j＋1～i個都用第i號的電源。答案為d[n]。

AC代碼：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <cmath>#define INF 0x3f3f3f3f#define FRER() freopen("in.txt", "r", stdin); #define FREW() freopen("out.txt", "w", stdout);using namespace std;struct lamp {int v, k, c, l;bool operator < (const lamp& temp) const {return v < temp.v;} };const int maxn = 1000 + 5;lamp light[maxn]; int n, dp[maxn], s[maxn];int main() {// FRER();// FREW();while(cin >> n, n) {for(int i = 1; i <= n; ++i) cin >> light[i].v >> light[i].k >> light[i].c >> light[i].l;sort(light + 1, light + n + 1);for(int i = 1; i <= n; ++i) s[i] = s[i - 1] + light[i].l;for(int i = 1; i <= n; ++i) {dp[i] = s[i] * light[i].c + light[i].k;for(int j = 1; j < i; ++j) dp[i] = min(dp[i], dp[j] + (s[i] - s[j])*light[i].c + light[i].k);}cout << dp[n] << endl;}return 0; }

?

轉載于:https://www.cnblogs.com/fan-jiaming/p/10059767.html

總結

以上是生活随笔為你收集整理的Lighting System Design UVA - 11400 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。