电源

[线性dp] Lighting System Design UVa11400

2019-07-14 02:49发布

站内文章 / 电源技术
10721 0 1391

题意

你的任务是设计一个照明系统。一共有n种灯泡可选，不同的灯泡需要不同的电源，而同一种灯泡可以共用一个电源。每种灯泡用4个值表示，所需电压V，电源价格K，灯泡单价C，所需个数L。为节省费用，可以用高电压灯泡代替低电压灯泡（如果能节省费用，且总灯泡数不能少）。求最少费用。

题解

题目的状态和动态转移方程不难写，但是有一个非常重要且有意思的预处理——按电压对所有灯泡排序。 做一个猜测，排序的预处理往往可以简化算法设计。

AC代码

#include #include #include #include #include using namespace std; const int maxn = 1000+1; const int INF = 0x3f3f3f3f; struct qurt{ int v, k, c, l; qurt(int v, int k, int c, int l):v(v),k(k),c(c),l(l){} bool operator < (const qurt& rhs)const{ return v ve; for(int i = 0; i=0; j--){ dp[i] = min(dp[i], dp[j]+(s[i]-s[j])*ve[i-1].c+ve[i-1].k); } } printf("%d ", dp[n]); } return 0; }  

热门文章