Description
Translation
题目大意：有一个照明系统需要用到n种灯，每种灯的电压为V，电源费用K，每个灯泡费用为C，需要该灯的数量为L。注意到，电压相同的灯泡只需要共享一个对应的电源即可，还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本，你将设计一种系统，使之最便宜。
Input
Sample Input
Sample Output
Hint
所有相同电压的灯泡共享一个电源。n<=1000。
Solution
注意到一种灯泡要么不换要么全换。
证明：如果灯泡只换一部分，那么说明被替换的一部分比不换省钱，那么全部换要比换那些省钱。如果不换，那么肯定都不换。
接下来考虑阶段，由于只能小灯泡换成大灯泡，也就是说小灯泡怎么选对大灯泡没有影响，所以考虑以电压v升序作为阶段。设前i种灯泡的最优解是f[i]。
则有状态转移方程：
f[i]=min{f[j]+(sum[i]-sum[j])*c+k}。其中sum为前缀和，表示区间[0,i]中的灯泡个数（非种类数）。
正确性证明：
方程的直观解释是先选取前j个的最优解，然后剩下的全部买i型电源。
考虑到可能被hack的数据是[j+1,i]中有几种不选电源i，选择更大的电源。那么原灯泡会适配大电源，大电源在转移时一定被选择，那么电源花费不变，如果购买大电源灯泡花费更少，那么第i个也会被转移，满足无后效性。故方程成立。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1010 inline void qr(int &x) {
char ch=getchar();int f=;
while(ch>''||ch<'') {
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
x*=f;
return;
} inline int max(const int &a,const int &b) {if(a>b) return a;else return b;}
inline int min(const int &a,const int &b) {if(a<b) return a;else return b;}
inline int abs(const int &x) {if(x>) return x;else return -x;} inline void swap(int &a,int &b) {
int c=a;a=b;b=c;return;
} int n,frog[maxn],sum[maxn]; struct Light {
int v,k,c,l;
};
Light MU[maxn]; void clear() {
std::memset(MU,,sizeof MU);
std::memset(frog,0x3f,sizeof frog);
std::memset(sum,,sizeof sum);
frog[]=;
} inline bool cmp(const Light &a,const Light &b) {return a.v<b.v;} int main() {
qr(n);
while(n) {
clear();
for(int i=;i<=n;++i) {
qr(MU[i].v);qr(MU[i].k);qr(MU[i].c);qr(MU[i].l);
}
std::sort(MU+,MU++n,cmp);
for(int i=;i<=n;++i) sum[i]=sum[i-]+MU[i].l;
for(int i=;i<=n;++i) {
for(int j=;j<i;++j) {
frog[i]=min(frog[i],frog[j]+(sum[i]-sum[j])*MU[i].c+MU[i].k);
}
}
printf("%d\n",frog[n]);
n=;qr(n);
}
return ;
}
Summary
需要排序的题，一定排序完再写前缀和！！！