UVa - 11400 - Lighting System Design(线性动态规划)
2019-07-14 00:02发布
生成海报
题目意思是 小灯泡(低电压)可以换成大灯泡,但是需求的数目不变,一种灯泡只买一个电源就可以。
举个例子 灯泡a和b。
a 电压 1 电源 50元 单价 5 需要 5
b 电压 2 电源 20元 单价 6 需要 4
买小灯泡的话,需要50+5*5=75 加上大灯泡的20+4*6+75 = 119元
如果把小灯泡换成大灯泡,虽然单价大灯泡贵,但是就不用买小灯泡的电源,就需要20+(5+4)*6 = 74元
现在就是给了一些灯泡 ,求出最省钱的方案
设dp[ i ] 是前 i 个灯泡的最优解 ,dp [ i ] = max ( dp [ i ] , dp [ j ] + ( sum [ i ] - sum [ i ] ) * 单价);
#include
#include
#include
#define N 1005
#define INF 1000000000
using namespace std;
struct Lamp{
int v,k,c,l;
}lamp[N];
bool cmp(Lamp p1 ,Lamp p2){
return p1.v
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮