UVa 11400 - Lighting System Design(线性DP)
2024-10-19 12:37:28
链接:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2395
题意:
有n(n≤1000)种灯泡,不同种类的灯泡必须用不同的电源,但同一种灯泡可以共用一个电源。
每种灯泡用4个数值表示:电压值V(V≤132000),电源费用K(K≤1000),灯泡单价C(C≤10)和所需数量L(1≤L≤100)。
可以把一些灯泡换成电压更高的另一种灯泡以节省电源的钱(但不能换成电压更低的灯泡)。求最优方案的费用。
分析:
首先可以得到一个结论:每种灯泡要么全换,要么全不换。因为如果把1个灯泡A换成灯泡B能省钱的话,干脆全换得了。
先把灯泡按电压值从小到大排序,这样的话前面的灯泡可以换成后面的灯泡,反之不行。
然后依次考虑每一种灯泡,对于第i种灯泡,尝试将前x(0≤x<i)种灯泡用原来的最优方案,后面的灯泡全用第i种。
为什么是后面的(即连续的)呢?有没有不连续的情况呢?比如灯泡A,B,C(按电压值升序),会不会有A换成C,
而B不换成C的情况呢?答案是没有的。因为如果B不换成C,则必然有:电源B + 单价B * 数量B < 单价C * 数量B。
可见A换成B更优,所以不会出现这种情况。
设sum[i]为前i种灯泡的总数量(即L值之和),d[i]为前i种灯泡的最小费用,
则d[i] = min{d[j] + (sum[i]-sum[j])*c[i] + k[i]},0≤j<i(d[0]表示全用第i种)。答案为d[n]。
代码:
#include <cstdio>
#include <algorithm>
using namespace std; const int UP = + ;
struct LAMP {
int V, K, C, L; //电压,电源费,单价,数量
bool operator < (const LAMP& that) const {
return V < that.V;
}
} a[UP]; int sum[UP], d[UP]; //sum[x]表示前x种灯泡的总数量,d[x]表示前x种灯泡的最小费用 int main(){
int n;
while(scanf("%d", &n) && n){
for(int i = ; i < n; i++)
scanf("%d%d%d%d", &a[i].V, &a[i].K, &a[i].C, &a[i].L);
sort(a, a + n); sum[] = a[].L;
for(int i = ; i < n; i++) sum[i] = sum[i-] + a[i].L;
for(int i = ; i < n; i++){
d[i] = sum[i] * a[i].C + a[i].K; //前sum[i]个灯泡都用类型i
for(int t = ; t < i; t++)
d[i] = min(d[i], d[t] + (sum[i] - sum[t]) * a[i].C + a[i].K);
}
printf("%d\n", d[n-]);
}
return ;
}
最新文章
- Selenium Webdriver下click失效问题解决
- jquery获取复选框的值
- C++之路进阶——bzoj3876(支线剧情)
- Android中插件开发篇之----类加载器
- textfield设置左边距
- Type datetime2 is not a defined system type - Entity Framework 摘自网络
- Linux内核--网络栈实现分析(二)--数据包的传递过程--转
- mysql查看表的结构
- (LightOJ 1030)期望dp
- java synchronized与volatile的区别
- ArcGIS添加鹰眼
- Zabbix的数据表结构
- CSS属性合写
- x64类型的程序逆向思考
- Android WebView的HTML中的select标签不起作用
- DBA思考系列——凛冬将至,丧钟为谁而鸣!
- winform SerialPort串口通信问题
- ctrl + alt + T无法启动终端
- spring注解第07课 @Valid和@Validated的总结区分
- Android app 在线更新那点事儿(适配Android6.0、7.0、8.0)