uva 11400 - Lighting System Design

//  uva 11400 - Lighting System Design
/*
  照明系统设计
  使用四个变量标记一个 灯泡
  电压V ， 电源价格K  ， 灯泡价格C， 灯泡数量L
  首先应该想到:替换时要不全部替换，要不就是不替换。
  假设 i比j单价大，那么使用i替换j的话 ，如果只替换一部分，则单价价格肯定会高，当全部替换时j中的电源的价格与替换后单价增加的cost会抵消(到底有没有降低总消费，还需比较）。
      i单价比j低，那么使用i替换j的话，如果只替换一部分，则单价会减少，在这个基础上再替换，单价仍会减少，当全部替换时
      单价减少的同时也去除了电源的价钱。
  因此:对于替换某种灯泡。要不全部替换，要不就不替换。
 我们先按灯泡的电压排序。
  此处是个多决策问题。对于第i种灯泡我们有2种 ， 1.使用它替换某些灯泡
                                         2.不替换任何灯泡
  当替换时，是替换那个或哪些呢。这就产生问题了。
  假设i替换 j 而j+1....i未替换，是最小cost ，那么j+1的单价一定大于i,j+2的单价大于j+1....i-1的单价大于i-2,i的价格大于i+1,那么 i 的单价大于j+1的单价，与前面矛盾。所以如果发生替换，则替换必定是从所使用的那个灯泡开始向前一直替换。
 */
#include <iostream>
#include <queue>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<vector>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <cstdio>
#define ll long long
using namespace std ;
int sum[1010] ;
int dp[1010] ;
int t[1010] ;
struct bulb
{
    int k ;
    int v , c,l ;
    bool operator < (const bulb &n ) const{
        return  v < n.v ;
    } ;
};
bulb b[1010] ;
int min(int a,  int b)
{
    return a > b ? b:a ;
}

int main(int argc, const char * argv[]) {
    int n ;
    while (scanf("%d" ,&n),n) {
        for (int i = 0; i < n ; i++) {
            scanf("%d%d%d%d" , &b[i].v ,&b[i].k,&b[i].c,&b[i].l)  ;
        }
        sort(b,b+n) ;
        sum[0] = b[0].l ;
        for (int i  = 1; i < n; i++) {
            sum[i] = 0 ;
            sum[i] = (sum[i-1] +b[i].l);
        }
        dp[0] = b[0].k + b[0].c *b[0].l ;
        for (int i = 1; i <n ; i++) {
            dp[i] = dp[i-1] + b[i].l*b[i].c + b[i].k ;
            dp[i] = min(dp[i] ,sum[i]* b[i].c + b[i].k ) ;
            for (int j = 1; j < i  ; j++) {
                  dp[i] = min(dp[i] ,dp[j-1] +  (sum[i]- sum[j-1]) * b[i].c + b[i].k) ;
            }
        }
        printf("%d\n" ,dp[n-1] );
    }
    
    return 0;
}