UVA 11400 Lighting System Design 照明系统设计

首先是一个贪心，一种灯泡要么全都换，要么全都不换。

先排序，定义状态d[i]为前面i种灯泡的最小花费，状态转移就是从d[j]，j<i，加上 i前面的j+1到i-1种灯泡换成i的花费。

下标排序玩脱了。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+3;

int V[maxn], K[maxn], C[maxn], L[maxn];
int d[maxn],r[maxn],s[maxn];
bool cmp(int a,int b) { return V[a]<V[b]; }
int main()
{
    //freopen("in.txt","r",stdin);
    int n; s[0] = 0;
    while(scanf("%d",&n),n){
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d%d",V+i,K+i,C+i,L+i);
            r[i] = i;
        }
        sort(r+1,r+1+n,cmp);
        for(int id = 1; id <= n; id++){
            int i = r[id];
            s[id] = s[id-1] + L[i];
            d[id] = s[id]*C[i] + K[i];
            for(int id2 = 1; id2 < id; id2++){
                int j = r[id2];
                d[id] = min(d[id],d[id2]+(s[id]-s[id2])*C[i]+K[i]);
            }
        }
        printf("%d
",d[n]);
    }
    return 0;
}