电源

uva11400Lighting System Design(简单DP+贪心)

2019-07-14 03:21发布

站内文章 / 电源技术
14426 0 1375
题目大意：有一个照明系统需要用到n种灯，每种灯的电压为V，电源费用K，每个灯泡费用为C，需要该灯的数量为L。注意到，电压相同的灯泡只需要共享一个对应的电源即可，还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本，你将设计一种系统，使之最便宜。 分析：首先需要明确一种灯泡要么全部换，要么不换。如果换一部分的话，首先电源费用得不到节约，那么节约的部分就只来自于换的那部分灯泡，既然可以节约钱干嘛不干脆全部换了呢？所以要么全换，要么不换。然后我们的算法就是先按照V排序，然后cost[i]表示解决前 i 种灯泡的最优解，那么转移方程是枚举j 如果我要用第i种灯泡去替换前面的灯泡，那么一定是连续的替换，不可能出现间断，这也是这个问题的核心所在，他的原因很简单，给出一个排列，1,2,3,4,5。5向前替换，不可以出现4没有被替换，而3却被5替换的现象，因为这一定不是最优方案，4不被替换一定是比5更好，那么3就应该被4替换，而不该被5替换，这样对于4又是连续的替换了。 所以区间替换是正确的，也是这里最巧妙的，这样正确的限制决策成功方便了状态转移，并且不会丢失解。 #include #include #include #include using namespace std; const int maxn = 1e3 + 5; struct node { int v, k, c, l; bool operator < (const node &a) const { return v < a.v; } }a[maxn]; int dp[maxn], sum[maxn]; int main() { int n; while(~scanf("%d", &n), n) { for(int i = 1; i <= n; i++) cin >> a[i].v >> a[i].k >> a[i].c >> a[i].l; sort(a+1, a+1+n); dp[0] = sum[0] = 0; for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i].l; for(int i = 1; i <= n; i++) { dp[i] = sum[i]*a[i].c + a[i].k; for(int j = i - 1; j >= 1; j--) dp[i] = min(dp[i], dp[j]+(sum[i]-sum[j])*a[i].c + a[i].k); } cout << dp[n] << endl; } return 0; }

热门文章