题解 UVA11400 【照明系统设计 Lighting System Design】

· · 题解

状态的定义：按额定电压排序后,dp[i]:表示前i个物品,以第i个物品结尾的最小费用

状态的转移：dp[i]这个状态由dp[j]转移而来，其中j+1到i的物品都被替换成第i个物品。

时间复杂度：O(N^2)

看了一些题解，好像都没说为什么"j+1到i的物品都被替换成第i个物品"这样做是合理的。

当然我也想了一个下午才明白了，下面大致说一下：

假设排序后物品序号如下：1，... ，i，i+1，i+2，...

假如我们在更新这个方程

dp[i+2] = std::min(dp[i+2], dp[i-1] + {i~i+2都被替换成第i+2个物品的花销})

此时一个直观的疑问是：问什么i,i+1,i+2都被替换成i+2这个物品，难道不可以只是第i个物品被替换成i+2这个物品，而第i+1个物品保持原样即不被i+2这个物品替换。

大家可以想象下，第i个物品和第i+2个物品很昂贵，而第i+1个物品很便宜。如下面这组数据：

//额定电压，电压源，每个灯泡的费用，数量

第i个物品：10,300,100,100

第i+1个物品：100,１,1,1

第i+2个物品：200,300,100,100

这样的话i,i+1,i+2都被替换成i+2,此时要：300+(100)*(100+1+100)

而i, i+2都被替换成i+2,而i+1保持不变，此时要：300+ 100*(100+100) + 1+1x1

此时发现后一种比前一种还要便宜，是不是我们将连续的一段如i,i+1,i+2都替换成i+2是错误的呢？

其实不是

大家接着思考一下，我们在更新dp[i+2]的时候，是不是dp[i+1]已经被更新过了，在更新dp[i+1]的时候已经把第i个物品替换成i+1这个物品了

此时虽然dp[i+2]从 {dp[i-1]这个状态 + 将i到i+2都替换成i+2这个物品}转移过来不是最优的，但是dp[i+2]也可以从dp[i+1]这个状态转移过来呀。

所以dp[i]在状态转移的时候，将连续的一段都替换成第i个物品是合理的，它不会丢失最优解。

//
// created by **** on 2019-08-17
//

#include <bits/stdc++.h>

const int maxn = 1e3 + 10;
int n;
// 按额定电压排序后,dp[i]:表示前i个物品,以第i个物品结尾的最小费用
// 因为前i个物品中,排序后第i个物品的额定电压最大，所以它是不能被其他物品替换的，所以第i个物品
// 一定是结尾，这里只是显示的定义出来。
int dp[maxn],sum_[maxn];

struct node{
    // 额定电压,电压源,费用,数量
    int voltage_rating;
    int voltage_source;
    int cost;
    int number;
    // 额定电压从小到大排序
    const bool operator< (const node& rhs) const{
        return voltage_rating < rhs.voltage_rating;
    }
}A[maxn];

int main(){
    while(scanf("%d",&n) && n){
        memset(sum_, 0, sizeof sum_);
        memset(dp, 0x3f3f3f, sizeof dp);
        dp[0] = 0;
        for(int i=1;i<=n;++i){
            scanf("%d %d %d %d",&A[i].voltage_rating, &A[i].voltage_source, &A[i].cost, &A[i].number);
        }

        // 排序以及前缀和
        std::sort(A+1,A+1+n);
        for(int i=1;i<=n;++i){
            sum_[i] = sum_[i-1] + A[i].number;
        }
        // dp过程
        for(int i=1;i<=n;++i){
            for(int j=0;j<i;++j){
                dp[i] = std::min(dp[i], dp[j] + (sum_[i]-sum_[j])*A[i].cost + A[i].voltage_source);
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}