Description

你的任务是设计一个照明系统。一共有n（n≤1000）种灯泡可供选择，不同种类的灯泡必须用不同的电源，但同一种灯泡可以共用一个电源。每种灯泡用4个数值表示：电压值V（V≤132000），电源费用K（K≤1000），每个灯泡的费用C（C≤10）和所需灯泡的数量L（1≤L≤100）。 假定通过所有灯泡的电流都相同，因此电压高的灯泡功率也大。为了省钱，可以把一些灯泡换成电压更高的另一种灯泡以节省电源的钱（不能换成电压更低的灯泡）。计算出最优方案的费用。

Input Data

Each case in the input begins with n (1 ≤ n ≤ 1000), denoting the number of categories. Each of the
following n lines describes a category. A category is described by 4 integers - V (1 ≤ V ≤ 132000), the
voltage rating, K (1 ≤ K ≤ 1000), the cost of a voltage source of this rating, C (1 ≤ C ≤ 10), the cost
of a lamp of this rating and L (1 ≤ L ≤ 100), the number of lamps required in this category. The input
terminates with a test case where n = 0. This case should not be processed.

Output Data

For each test case, print the minimum possible cost to design the system.

Input sample

3
100 500 10 20
120 600 8 16
220 400 7 18
0

Output sample

778

Hint

input data和output data 的英文意思可以忽略 ——————————————————分割の线————————————————————

分析

易知，换一个灯泡不如全部换，证明如下：
若换一个灯泡亏钱，那无论换多少个都是亏，除非全换（可以省一个电池钱）
若换一个灯泡省钱，那全换省的钱更多（并且可以再省一个电池钱）
如此，我们可以定义f[i]表示到第i种灯泡消耗的最小值
转移方程如下：
f[i]=min(f[i],f[j]+(s[i]-s[j])*a[i].c+a[i].k);(0<=j < i)
表示从i+1到j种灯泡全都换成j种的灯泡，开销最少为多少 其中用前缀和来维护前i种灯泡的数量，变量为s[i]
完整代码如下： #include #include #include #include using namespace std; struct node { int v,k,c,l; }a[1010];//v为电压，k为电源价格，c为灯泡价格，l为灯泡数目 int n,s[1010];//用s维护前缀和 int f[1010];//dp核心 int cmp(node x,node y) { return x.v//排序，使得灯泡按照电压大小排序 int main() { scanf("%d",&n); while(n!=0) { for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l); sort(a+1,a+n+1,cmp); s[0]=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].l;//计算前缀和 f[1]=a[1].k+a[1].c*s[1];//f[1]即为最低电压灯泡所负担的开销 for(int i=2;i<=n;i++) { f[i]=f[0]+(s[i]-s[0])*a[i].c+a[i].k;//保底赋值 for(int j=1;j//在f[j]最小的基础上，将i+1到j种灯泡都变为第j种的最小开销 } printf("%d ",f[n]); scanf("%d",&n);//注意可能的多次输入 } return 0; }