题解 | #Lighting System Design#

紫书经典题目了
思路就是dp
这里有个点就是一个种类的灯泡要么不换，要么全换，因为你换一半的时候需要两个电源的费用，而且你要换的话肯定往便宜的换，那肯定全换
先按电压从小到大排序
令d[i]为前i个种类的灯泡的最小费用
那怎么找呢
我们可以先让d[i]为前i个种类的全部灯泡全部转化成第i个种类的灯泡
则我们用一个j遍历1到i
而前j个种类的灯泡我们就用d[j]表示最优解的时候
让后面i-j个种类的灯泡都转化为第i号电源
再相加
方程就出来了
d[i]=min(d[i],d[j]+(sum[i]-sum[j])*a[i].c+a[i].c)

AC代码

#include <bits/stdc++.h>

using namespace std;
struct node
{
    int v,k,c,l;
} a[1010];
int n;
int d[1010];
int sum[1010];
int main()
{
    while(cin>>n&&n)
    {
        for(int i=1; i<=n; i++)cin>>a[i].v>>a[i].k>>a[i].c>>a[i].l;
        sort(a+1,a+1+n,[](node x,node y){return x.v<y.v;});
        for(int i=1; i<=n; i++)sum[i]=sum[i-1]+a[i].l;
        for(int i=1; i<=n; i++)
        {
            d[i]=sum[i]*a[i].c+a[i].k;//先将前i个种类的全部灯泡转化成电压为a[i].v的灯泡
            for(int j=1; j<i; j++)
                d[i]=min(d[i],d[j]+(sum[i]-sum[j])*a[i].c+a[i].k);
        }
        cout<<d[n]<<endl;
    }
    return 0;
}