设计一个照明系统,一共有n(n<=1000)种灯泡可供选择,不同种类的灯泡必须用不同的电源,同一种灯泡则可以用一个,输入为一个n,以下n行,每行四个数值,代表电压V,电源费用K,每个灯泡费用C,所需灯泡数量L。n=0为结束标志。
为了省钱,你可以把一些灯泡换成电压更高的以节省电源的钱,但不能换成更低的,请你计算出最优方案的费用。
首先,一种灯泡要么不换,要么全部换
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N =1003; struct T{ int v,k,c,l; } a[N]; int n,s[N],f[N]; int cmp(T &x,T &y){ return x.v<y.v; } void sov(){ int i,j; f[0]=0; for(i=1;i<=n;i++) for(j=0 ;j<i;j++) f[i]=min(f[i],f[j]+a[i].k+a[i].c*(s[i]-s[j])); cout<<f[n]<<'\n'; } signed main(){ while(cin>>n,n){ for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].k>>a[i].c>>a[i].l; sort(a+1,a+1+n,cmp); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].l ; sov(); } }
标签:int,System,Lighting,uva11400,Design,include From: https://www.cnblogs.com/towboa/p/17301321.html