Lighting System Design （区间dp）

      题意很不好理解，输入给的是N个灯泡的参数，然后一个电池可以带好多个灯泡，电压高的电池可以给电压低的灯泡用（反过来不行）。

代码：

/*
    给n个灯泡：
      v:  所需电压
      k:  电压价格
      c:  灯泡价格
      l:  灯泡所需个数
    要求：  低电压灯泡可以使用高电压电池，一个电池可以带多个灯泡
            求 最少花费？
    分析： ① 要买够灯泡
           ② 考虑 换电池
    方法： 按电池电压排序，后面的一定能换前面的，
             再加以判断
*/

#if 0

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
    int v, k, c, l;
}nd[1010];
int sum[1010];
int dp[1010];
int cmp(Node a, Node b)
{
    return a.v<b.v;
}
int main()
{
    int N;
    while(cin>>N && N)
    {
        for(int i=1; i<=N; i++)
        {
            cin>>nd[i].v>>nd[i].k>>nd[i].c>>nd[i].l;
        }
        sort(nd+1, nd+N+1, cmp);
        memset(sum, 0, sizeof(sum));
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=N; i++)
        {
            sum[i]=sum[i-1]+nd[i].l;
        }
        for(int i=1; i<=N; i++)
        {
            dp[i]=sum[i]*nd[i].c+nd[i].k;
            for(int j=1; j<i; j++)
            {
                dp[i]=min(dp[i], dp[j]+(sum[i]-sum[j])*nd[i].c+nd[i].k);
            }
        }
        cout<<dp[N]<<endl;
    }

    return 0;
}