【動态規劃】Lighting System Design 照明系統設計

Description

你的任務是設計一個照明系統。一共有n（n≤1000）種燈泡可供選擇，不同種類的燈泡必須用不同的電源，但同一種燈泡可以共用一個電源。每種燈泡用4個數值表示：電壓值V（V≤132000），電源費用K（K≤1000），每個燈泡的費用C（C≤10）和所需燈泡的數量L（1≤L≤100）。

假定通過所有燈泡的電流都相同，是以電壓高的燈泡功率也大。為了省錢，可以把一些燈泡換成電壓更高的另一種燈泡以節省電源的錢（不能換成電壓更低的燈泡）。計算出最優方案的費用。

Input Data

Each case in the input begins with n (1 ≤ n ≤ 1000), denoting the number of categories. Each of the

following n lines describes a category. A category is described by 4 integers - V (1 ≤ V ≤ 132000), the

voltage rating, K (1 ≤ K ≤ 1000), the cost of a voltage source of this rating, C (1 ≤ C ≤ 10), the cost

of a lamp of this rating and L (1 ≤ L ≤ 100), the number of lamps required in this category. The input

terminates with a test case where n = 0. This case should not be processed.

Output Data

For each test case, print the minimum possible cost to design the system.

Input sample

3

100 500 10 20

120 600 8 16

220 400 7 18

Output sample

778

Hint

input data和output data 的英文意思可以忽略

——————————————————分割の線————————————————————

分析

易知，換一個燈泡不如全部換，證明如下：

若換一個燈泡虧錢，那無論換多少個都是虧，除非全換（可以省一個電池錢）

若換一個燈泡省錢，那全換省的錢更多（并且可以再省一個電池錢）

如此，我們可以定義f[i]表示到第i種燈泡消耗的最小值

轉移方程如下：

f[i]=min(f[i],f[j]+(s[i]-s[j])*a[i].c+a[i].k);(0<=j < i)

表示從i+1到j種燈泡全都換成j種的燈泡，開銷最少為多少

其中用字首和來維護前i種燈泡的數量，變量為s[i]

完整代碼如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int v,k,c,l;
}a[];//v為電壓，k為電源價格，c為燈泡價格，l為燈泡數目
int n,s[];//用s維護字首和
int f[];//dp核心
int cmp(node x,node y)
{
    return x.v<y.v;
}//排序，使得燈泡按照電壓大小排序
int main()
{
    scanf("%d",&n);
    while(n!=)
    {
        for(int i=;i<=n;i++)
            scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l);
        sort(a+,a+n+,cmp);
        s[]=;
        for(int i=;i<=n;i++)
            s[i]=s[i-]+a[i].l;//計算字首和
        f[]=a[].k+a[].c*s[];//f[1]即為最低電壓燈泡所負擔的開銷
        for(int i=;i<=n;i++)
        {
            f[i]=f[]+(s[i]-s[])*a[i].c+a[i].k;//保底指派
            for(int j=;j<i;j++)
                f[i]=min(f[i],f[j]+(s[i]-s[j])*a[i].c+a[i].k);//在f[j]最小的基礎上，将i+1到j種燈泡都變為第j種的最小開銷
        }
        printf("%d\n",f[n]);
        scanf("%d",&n);//注意可能的多次輸入
    }
    return ;
}