[中等] UVa OJ 11400 Lighting system design 動态規劃

題目描述

基本思路：（類比最長上升子序列LIS問題）

首先，對于每種電源的燈泡要麼全換，要麼不換，因為不能将大電壓的燈泡換成小電壓的，是以先将燈泡按電壓大小排序，排完序後，就是一個考慮第i種燈泡換不換的問題了，是個多階段決策問題，是以考慮動态規劃。設d[i]為前i種燈泡的最小費用，s[i]為前i種燈泡的總數，c[i]為第i種燈泡的單價，k[i]為第i種燈泡的電源價格，則狀态轉移方程為：

d[i]=min{d[j]+(s[i]-s[j])*c[i]+k[i]}，0=<j<=i，1<=i<=n

注意，上式中當j為0時表示将之前的所有燈泡全部換為第i種。邊界條件d[0]=0

具體代碼：

#include <iostream>
#include <algorithm>

using namespace std;
struct lamp
{
    int v,k,c,l;
    bool operator < (const lamp& rhs) const
    {
        return v<rhs.v;
    }
};
const int maxn=1000+5;
lamp lp[maxn];
int s[maxn];
int d[maxn];
int main()
{
    int n;
    for(cin>>n;n!=0;cin>>n)
    {
        for(int i=1;i<=n;++i)
        {
            cin>>lp[i].v>>lp[i].k>>lp[i].c>>lp[i].l;
        }
        sort(lp+1,lp+1+n);
        s[0]=0;
        for(int i=1;i<=n;++i)
        {
            s[i]=s[i-1]+lp[i].l;
        }
        d[0]=0;
        for(int i=1;i<=n;++i)
        {
            d[i]=d[i-1]+lp[i].l*lp[i].c+lp[i].k;
            for(int j=0;j<i;++j)
                d[i]=min(d[i],d[j]+(s[i]-s[j])*lp[i].c+lp[i].k);
        }
        cout<<d[n]<<endl;
    }
    return 0;
}