F - Lighting System Design UVA - 11400

 

F - Lighting System Design

 UVA - 11400 

1.首先得到一个结论，每种电压的灯泡要么全换，要么全不换。如果只换部分灯泡，则不能节省电源的费用。

2.把灯泡按从小到大的顺序排。设s【i】为前i种灯泡的总数量  //我开始忘记排序了老是WA

3.d【i】为第1-i种灯泡的最小开销。状态转移方程d【i】=min{d[i],d[j]+(s[i]-s[j])*c[i]+k[i]}表示前j种灯泡不变 把j+1~i种灯泡换成第【i】种灯泡的电源。答案为d【n】。

4.i的范围自然是1-n，因为一共有n种电源。但是j的范围是0到i，等于0的时候表示把所有的灯泡都换成第i种，等于i的时候表示所有的灯泡都不换，按它原来的方案进行。

#include <iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n;
int d[1005];
int s[1005];
int INF=0x3f3f3f3f;
struct Light
{
    int v,k,c,l;
}light[1005];
bool cmp(Light a,Light b)
{
    return a.v<b.v;
}
int main()
{
    //freopen("E:\\file.txt","r",stdin);
    while(cin>>n&&n)
    {
    s[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&light[i].v,&light[i].k,&light[i].c,&light[i].l);  //分别为个数 电源费用 每个灯泡的费用 所需灯泡的个数
    }
    memset(d,0x3f,sizeof(d));
    sort(light+1,light+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+light[i].l;
    }

    d[0]=0;
    d[1]=light[1].k+light[1].c*light[1].l;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
    {
        d[i]=min(d[j]+(s[i]-s[j])*light[i].c+light[i].k,d[i]); //d[i]表示前j种先用最优方案买，第j+1到第i
        //都用第i号的电源 答案为d[n]
    }
    cout<<d[n]<<endl;
    }



    return 0;
}