紫皮书题:
题意:让你设计照明系统,给你n种灯泡,每种灯泡有所需电压,电源,每个灯泡的费用,以及每个灯泡所需的数量。每种灯泡所需的电源都是不同的,其中电压大的灯泡可以替换电压小的灯泡,要求求出最小费用
题解:每种电压灯泡要么全换,要么全不换,因为只换部分还要加额外的电源费用,并且换了部分之后费用更少,不如全换
先把灯泡按照电压从小到大排序,这样进行dp时,后面的电压大的如果比电压小的更优的话就可以替换了
设dp[j]为前j个最优了,则dp[i] = min{dp[i],dp[j] + (s[i]-s[j]) * c[i] + k[i]} dp[i]在使用前要初始化为最大
s为前i种灯泡的总数量,s[i] - s[j]表示从 i 到 j 替换为 i 则费用为 (s[i] - s[j]) * c[i] + k[i] 还要加上前 j 个灯泡的费用 dp[j];
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
const int INF = 0xfffffff;
const double ESP = 10e-;
const double Pi = atan() * ;
const int MOD = ;
const int MAXN = + ;
typedef long long LL;
using namespace std; struct Light{
int v,k,c,l;
bool operator < (Light a)const{
return v < a.v;
}
}; Light light[MAXN];
LL dp[MAXN];
LL s[MAXN]; int main(){
// freopen("input.txt","r",stdin);
int n;
while(~scanf("%d",&n) && n){
for(int i = ;i <= n;i++){
scanf("%d%d%d%d",&light[i].v,&light[i].k,&light[i].c,&light[i].l);
}
sort(light+,light+n+);
s[] = ;
for(int i = ;i <= n;i++){
s[i] = light[i].l + s[i-];
}
dp[] = ;
for(int i = ;i <= n;i++){
dp[i] = INF;
for(int j = ;j <= i;j++){
dp[i] = min(dp[i],dp[j]+(s[i] - s[j]) * light[i].c + light[i].k);
}
}
printf("%lld\n",dp[n]);
}
return ;
}