20180520-DP2 E - Lighting System Design

位址：點選打開連結

DP思維題，算是比較簡單的題目，一開始讀題意感覺到很難懂，讀了好久，現在簡單描述一下題意。

有一些燈泡，每個燈有四個值

V  該燈泡的電壓，可以買電壓高的燈泡代替電壓低的燈泡，電壓兩兩不同

K  發電機價格，隻有有一台，就可以供應無限多個該電壓的燈泡

C 燈泡價格

L  這個電壓的燈泡需要多少隻

問買完所有要求的燈泡的最小花費

思路：

注意，因為是高電壓的點燈可以替換低電壓，這種情況還需要買一個發電機，是以可以先對電壓進行排序，那麼後面的一定可以替換前面的，然後兩重循環進行比較，确定結果。

dp[i]=min(dp[i],dp[j]+la[i].k+la[i].c*(sum[i]-sum[j]));

表示買了i發電機，dp[j]表示買好前j個燈泡的最優解，然後加上買發電機的錢，再加上購買剩下的燈泡的錢，就是總的花費了。取個最小值就是購買前i個燈泡的最優解了。

代碼：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7f7f7f7f
int n;
struct Lamp{
    int v;
    int k;
    int c;
    int l;
}lamp[10010];

int sum[1010];
int dp[1010];

int cmp(Lamp a,Lamp b)
{
    return a.v<b.v;
}

int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0) break;

        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %d %d",&lamp[i].v,&lamp[i].k,&lamp[i].c,&lamp[i].l);
        }

        sort(lamp+1,lamp+n+1,cmp);

        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+lamp[i].l;
        }

        memset(dp,INF,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                dp[i]=min(dp[i],dp[j]+lamp[i].k+lamp[i].c*(sum[i]-sum[j]));
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}
           

• ，然後加上買發電機的錢