UVA Lighting System Design

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int s[1005];//表示前i中灯泡总的数量
int d[1005];//表示最小的开销
struct node
{
	int v,k, c, l;
	bool operator<(const node &res)const
	{
		return v < res.v;
	}
}kind[1005];//结构体数组内进行优先级排序
int main()
{
	int t;
	while (scanf("%d", &t)==1 && t)
	{
		memset(kind, 0, sizeof(kind));
		memset(d, 0, sizeof(d));
		memset(s, 0, sizeof(s));
		for (int i = 1; i <= t; i++)
		{
			scanf("%d %d %d %d", &kind[i].v, &kind[i].k, &kind[i].c, &kind[i].l);
		}
		sort(kind+1 , kind + 1+t);//调用排序,注意数组的赋值小标从1开始
		s[0] =0;//注意初始化细节
		for (int i = 1; i <= t; i++)
			s[i] = s[i - 1] + kind[i].l;
		for (int i = 1; i <= t; i++)
		{
			d[i] = s[i] * kind[i].c + kind[i].k;
		}//完全购买相同种类的灯泡，注意初始化
		for (int i = 1; i <= t; i++)
		{
			for (int j = 1; j <=i; j++)//控制i,j关系,注意细节控制
			{
				d[i] = min(d[i], d[j] + (s[i] - s[j])*kind[i].c + kind[i].k);//注意每种灯泡要么全部更换，要么全部都不进行更换
			}//注意灯泡更换的细节，同种类型应保持一致
		}
		printf("%d\n", d[t]);
	}
	getchar();
	getchar();
	return 0;
}

1、本题重要结论，注意更换灯泡的细节，保持成本最低，更换灯泡时应满足要么全部更换灯泡，要么同种类型的灯泡都不更换，状态转移便根据不同类型的灯泡依次更换进行，d[j]表示前j个用最佳的方案，后面的j+1个灯泡更换为电压为kind[i].v的灯泡，进行费用的更新，目的在于节省电压的费用

2、注意初始化的细节，d[i]先初始化为全买相同类型的灯泡，同时注意利用s[i]对于灯泡数量的控制内层循环的控制,j<=i，注意相应细节