题目链接 https://cn.vjudge.net/problem/UVA-11400【题意】    你的任务是设计一个照明系统，一共有n（n<=1000）个灯泡可以选择，不同种类的灯必须使用不同的电源，但同种灯泡可以共用一个电源，每种灯泡有4个属性，电压V（V<=132000），电源费用K（K<=1000），每个灯泡的费用C（C<=10）和每种灯泡的数量L（L<=100）
    为了省钱，你可以把一些低电压灯泡换成电压更高的灯泡，你的任务是计算出最优方案的费用是多少。
【输入格式】    第一行为一个整数n，表示有n中不同的灯泡，n=0代表输入结束。下面n行每行4个整数，分别是每种灯泡的电压，电源费用，单价和数量。
【输出格式】    输出一个整数即最小费用。【样例输入】3 100 500 10 20 120 600 8 16 220 400 7 18 0  【样例输出】778 【思路】    这道题有两个最绕的地方。我先说结论再证明，第一个是对于某种灯泡来说，要么干脆全不换，要么干脆全都换成更高电压的一种灯泡。第二个是如果我们按照电压升序的规则对每种灯泡排序，那么一定是把连续的一段对应的灯泡换掉才能产生最优解，举个例子说，假如有若干种灯泡已经按照电压排好顺序，那么用第四种灯泡替换掉第一种和第三种一定不是最优解，用第四种把前三种全换掉一定更优！    证明如下。先说第一条，直观理解，如果说现在有两种灯泡，第一种的电压小于第二种。假设把第一种的若干个(不是全部)用第二种替换是最优解，那么也就说明第二种的单价一定小于第一种的，所以才能更省钱，那既然这样，直接全部把第一种换完，连第一种的电源都不用买不是更好么？所以原则是要么全换，要么全不换。当然我开始是拿数学式子推的，设两种灯泡k1,c1,l1;k2,c2,l2然后设用x件第二种灯泡换掉第一种，求花费的表达式w=k1+k2+c1*l1+c2*l2+(c2-c1)*x(x=c2时，上式>=下式，也就是说一定要拿单价小的灯泡把单价大的灯泡换掉。    对于第二条，想明白了这一点是dp的关键。就拿刚才的例子来说，假如有若干种灯泡已经按照电压排好顺序，假如用第四种灯泡替换掉第一种和第三种是最优解，那么第二种灯泡的单价一定小于第一种灯泡的单价（不然就不是最优了，应该直接那第四种把第二种也换掉才对呀），而如果说第二种灯泡的单价小于第一种灯泡，那么再拿第二种灯泡换掉第一种灯泡就可以产生一个更优解，与假设矛盾，所以也就证明了第二条结论。    设dp[i]是购买前i种灯泡的最小花费，则递推公式为dp[i]=min{dp[j]+(s[i]-s[j])*a[i].c+a[i].k|0<=j#include using namespace std; const int inf=2e9; const int maxn=1050; struct node{ int v,k,c,L; node(int vv=0,int kk=0,int cc=0,int LL=0):v(vv),k(kk),c(cc),L(LL){} bool operator<(const node& e)const{ return v>n && n){ memset(s,0,sizeof(s)); for(int i=0;i>v>>k>>c>>L; light[i]=node(v,k,c,L); } sort(light,light+n); s[0]=light[0].L; for(int i=1;i