題意：

看白書

要點：

其他的白書上講的比較清楚了，狀態轉移方程為：d[i] = min(d[i], d[j] + (s[i] - s[j])*bulb[i].c + bulb[i].k)，有點難以理解的是如果i到j之中有的不進行換比較合理怎么辦？但其實這種情況是不存在的，這個博客進行了詳細的數學推導：點擊打開鏈接

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; int d[1005], s[1005]; typedef struct node {int v, k, c, l; }node; node bulb[1005];bool cmp(node a, node b) {return a.v < b.v; }int main() {int n,i,j;while (scanf("%d", &n) && n){for (i = 1; i <= n; i++)scanf("%d%d%d%d", &bulb[i].v,&bulb[i].k,&bulb[i].c,&bulb[i].l);sort(bulb + 1, bulb + 1 + n, cmp);memset(d, inf, sizeof(d));memset(s, 0, sizeof(s));d[0] = 0;for (i = 1; i <= n; i++)s[i] = s[i - 1] + bulb[i].l;for (i = 1; i <= n; i++)for (j = 0; j < i; j++)d[i] = min(d[i], d[j] + (s[i] - s[j])*bulb[i].c + bulb[i].k);printf("%d\n", d[n]);}return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343735.html

總結

以上是生活随笔為你收集整理的例题9-6 UVa11400 Lighting System Design(DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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