题目链接 你的任务是设计一个照明系统。一共有n（n≤1000）种灯泡可供选择，不同种类的灯泡必须用不同的电源，但同一种灯泡可以共用一个电源。每种灯泡用4个数值表示：电压值V（V≤132000），电源费用K（K≤1000），每个灯泡的费用C（C≤10）和所需灯泡的数量L（1≤L≤100）。
假定通过所有灯泡的电流都相同，因此电压高的灯泡功率也更大。为了省钱，可以把一些灯泡换成电压更高的另一种灯泡以节省电源的钱（但不能换成电压更低的灯泡）。你的任务是计算出最优方案的费用。
【分析】
首先可以得到一个结论：每种电压的灯泡要么全换，要么全不换。因为如果只换部分灯泡，如V=100有两个灯泡，把其中一个换成V=200的，另一个不变，则V=100和V=200两种电源都需要，不划算（若一个都不换则只需要V=100一种电源）。先把灯泡按照电压从小到大排序。设s[i]为前i种灯泡的总数量（即L值之和），d[i]为灯泡1～i的最小开销，则d[i] = min{d[j] ＋ (s[i]－s[j])*c[i] ＋ k[i])}，表示前j个先用最优方案买，然后第j＋1～i个都用第i号的电源。答案为d[n]。 #include #include using namespace std; const int N =1000+5; int d[N],s[N]; struct LAMP{ int v, k, c, l; bool operator <(LAMP x){ return v < x.v; } }lamp[N]; int main(int argc, char** argv) { int n; while(cin>> n && n){ for(int i = 1; i <= n; i++) cin>> lamp[i].v>> lamp[i].k >> lamp[i].c>> lamp[i].l; sort(lamp+1, lamp+n+1); s[0] = 0; for(int i = 1; i <= n; i++){ s[i] = lamp[i].l +s[i-1]; d[i] = s[i]*lamp[i].c+lamp[i].k; // 前i个灯泡全买类型i for(int j = 1; j <= i; j++) d[i] = min(d[i],d[j]+(s[i]-s[j])*lamp[i].c+lamp[i].k); } cout<< d[n] << ' '; } return 0; }