Lighting System Design UVA - 11400（dp）

思路：根據題意，隻能用等級大的替換等級小的，是以先将燈排序，接下來就是如何替換的問題， 可以證明 替換一定是連續的替換，假如說有 a, b, c， d三個燈， 替換非連續替換，就是說d替換了a， c，沒有替換b， 這也就是說b的花費是足夠小，無法讓d替換，那麼b一定可以替換a，也就是說b替換了a， d替換了c；

是以轉移方程為 dp[i]=min(dp[i],  dp[j]+lamp[i].c*(s[i]-s[j])+lamp[i].k) //dp[i]代表前i個燈替換的最小花費。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
typedef long long ll;

struct node{
    ll v, k, c, l;
}lamp[N];

ll dp[N], s[N];

bool cmp(node a, node b){
    return a.v<b.v;
}

int main()
{
    int n;
    while(~scanf("%d", &n)&&n){
        for(int i=1; i<=n; i++){
            scanf("%lld%lld%lld%lld", &lamp[i].v, &lamp[i].k, &lamp[i].c, &lamp[i].l);
        }

        sort(lamp+1, lamp+1+n, cmp);
        memset(dp, 0x3f, sizeof(dp));
        memset(s, 0, sizeof s);
        dp[0]=0;
        for(int i=1; i<=n; i++){
            s[i]=s[i-1]+lamp[i].l;
            for(int j=i-1; j>=0; j--){
                dp[i]=min(dp[i], dp[j]+lamp[i].k+lamp[i].c*(s[i]-s[j]));
            }
        }

        printf("%lld\n", dp[n]);


    }

    return 0;
}