先按照电压从小到大排序,做一下前缀和s[i]求i之前的电灯泡的数量。
状态:$ F_i\(表示到\) i$个灯泡的最小开销。
状态转移方程:$ F_i=F_j+(s[i]-s[j])\times c_i + k_i$
答案是$ F_n$
#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\n",f[n]);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章