http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2395

首先可以得出一个结论,那就是换灯泡的时候,要么都不换,要么都换。(因为部分换的话电源就要买两种)
那么就可以把每种灯泡看成一个整体。

状态:dp[i]表示灯泡1~i的最小费用。
转移:前j个先用最优方案买,然后j+1~i都用第i种的电源,即dp[i]=min{dp[j]+(sum[i]-sum[j])*c[i]+k[i]}

const int mx = 1005;

struct Lamp
{
    int v, k, c, l;
    bool operator < (const Lamp& rhs) const
    {
        return v < rhs.v;
    }
} lamp[mx];

int n, s[mx], d[mx];

int main()
{
    while (cin >> n, n)
    {
        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);
        s[0] = 0;
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + lamp[i].l;
        d[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            d[i] = s[i] * lamp[i].c + lamp[i].k; /// 前i个灯泡全买类型i
            for (int j = 1; j <= i; j++)
                d[i] = min(d[i], d[j] + (s[i] - s[j]) * lamp[i].c + lamp[i].k);
        }
        cout << d[n] << endl;
    }
    return 0;
}

Comments

comments powered by Disqus