【Uva11400 Lighting System Design】动态规划

分析

先按照电压从小到大排序，做一下前缀和s[i]求i之前的电灯泡的数量。

状态：$ F_i(表示到) i$个灯泡的最小开销。

状态转移方程：$ F_i=F_j+(s[i]-s[j]) imes c_i + k_i$

答案是$ F_n$

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int Inf=1000000;
struct record{
    int v,k,c,l;
    bool operator <(const record &a) const{
        return v<a.v;
    }
}a[1005];
inline int read() {
    int x=0,w=0; char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return w?-x:x;
}
inline void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
int s[1005],f[1005];
int main(int argc,char* argv[]) {
    std::ios::sync_with_stdio(false);
    while (1) {
        int n=read(); if (n==0) break;
        for (int i=1;i<=n;i++) a[i].v=read(),a[i].k=read(),a[i].c=read(),a[i].l=read();
        sort(a+1,a+1+n);
        for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i].l;
        ms(f,Inf); 
        f[0]=0;
        for (int i=1;i<=n;i++) {
            for (int j=0;j<i;j++) {
                f[i]=min(f[i],f[j]+(s[i]-s[j])*a[i].c+a[i].k);
            }
        }
        printf("%d
",f[n]);
    }
    return 0;
}