欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Lighting System Design

程序员文章站 2022-06-06 17:06:09
...

Lighting System Design
UVA11400
定义dp[i]dp[i]为考虑前种中灯泡的最小花费,PrefixSum[i]PrefixSum[i]为前i种灯泡的需求量之和(前缀和)。
初始化

for (int i = 0; i < n; ++i) {
		dp[i] = lamps[i].K + PrefixSum[i] * lamps[i].C;
	}

即前i种灯泡的需求都由第i种灯泡满足。
转移方程:
显然,一个种类的灯泡要么不替换,要么全部替换成另一种灯泡。
首先先将灯泡种类按电压由底到高排序,这样在考虑dp[i]dp[i]时,第j(0j<i)j(0\leq j <i)个灯泡都可以被第ii个灯泡所替换,得到方程:
dp[i]=min(dp[i],dp[j]+(PrefixSum[i]PrefixSum[j])lamps[i].C+lamps[i].K)(0j<i)dp[i] = min(dp[i], dp[j] + (PrefixSum[i] - PrefixSum[j]) * lamps[i].C + lamps[i].K)(0\leq j<i)
即将第j+1j+1种灯泡到第i种灯泡都替换成第ii种灯泡。
AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
struct Lamp {
	int V, K, C, L;
}lamps[1000];
int dp[1001], PrefixSum[1001];
bool Input() {
	cin >> n;
	if (!n) {
		return false;
	}
	for (int i = 0; i < n; ++i) {
		int V, K, C, L;
		cin >> V >> K >> C >> L;
		lamps[i] = Lamp{ V,K,C,L };
	}
	return true;
}
void InitPrefixSum() {
	PrefixSum[0] = lamps[0].L;
	for (int i = 1; i < n; ++i) {
		PrefixSum[i] = PrefixSum[i - 1] + lamps[i].L;
	}
	return;
}
int DP() {
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i < n; ++i) {
		dp[i] = lamps[i].K + PrefixSum[i] * lamps[i].C;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			dp[i] = min(dp[i], dp[j] + (PrefixSum[i] - PrefixSum[j]) * lamps[i].C + lamps[i].K);
		}
	}
	return dp[n - 1];
}
int main() {
	ios::sync_with_stdio(false);
	while (Input()) {
		sort(lamps, lamps + n, [](const Lamp&Left,const Lamp&Right)->bool {
			return Left.V < Right.V;
			});
		InitPrefixSum();
		cout << DP() << endl;
	}
	return 0;
}