UVA 11400_ Lighting System Design

题意:

给定一系列灯泡的额定功率，电源价钱，一个灯泡的价格以及系统所需该种灯泡的数量。已知流过灯泡的电流相等，所以为省钱可以将电压小的灯泡换成电压大的灯泡，但是不能换成电压更小的灯泡，问最少要花多少钱。

分析：

首先要明确：

• 只要是电压大的比电压小的便宜，就一定要用大的替换小的灯泡。
• 替换必须是全部替换，不能替换一部分，即用某一种大的替换某种小的全部的灯泡。反正替换的灯泡个数没有限制，为什么不尽可能多的把又小又贵的灯泡替换掉，况且如果不全部替换，还要多交一份电源钱。

用大的替换小的，对于每一种灯泡，判断他是否可以替换某种小的，所以现将各种灯泡根据电压进行从小到大排序，定义dp[i]为使用前i种灯泡在满足需求的条件下所需最低价钱。状态转移方程：

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

其中1~j已经是最优安排，j~i则全部使用第i种灯泡，因为要保证最优结果，所以花费肯定是从小到大排列，所以如果需要替换，从第一个比第i个灯泡花费小到第i个灯泡之前的所有灯泡都要替换的。明确这些代码就很好写啦。

代码：

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = 1055, INF = 0x3fffffff;

int dp[maxn], s[maxn];

struct node{

    int v,k,c,l;

}lamp[maxn];

bool cmp(node a, node b)

{

    return a.v<b.v;

}

int main (void)

{

    int n;

    while(cin>>n&&n){

        fill(dp, dp + maxn,INF);

        dp[0]=0;

        fill(s, s+maxn,0);

        for(int i = 1; i <= n; i++)

                cin>>lamp[i].v>>lamp[i].k>>lamp[i].c>>lamp[i].l;

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

        for(int i = 0; i <= n; i++) s[i] = s[i-1]+lamp[i].l;

        for(int i = 1; i <= n ; i++){

          for(int j =0; j <= i; j++){

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

              }

          }

        cout<<dp[n]<<endl;

    }

    return 0;

}

看到问题还是要想清楚，想不清楚就多读几遍题，真正深入理解问题