uva 11400 - Lighting System Design(动态规划 最长上升子序列问题变

2019-07-14 00:27发布

本题难处好像是在于 可以把一些灯泡换成电压更高的灯泡以节省电源的钱 ,所以也才有了对最优方案的探求 好的处理方法是按照电压从小到大排序,只能让前面的换成后面的,也就满足了把一些灯泡换成电压更高的灯泡 的要求; 一种电压的灯泡,要么不换,要换则应该全换:换,说明用当前的电源不值;而既然不值则应该全部换掉以避免使用当前电源,不然即增加了灯泡费用又没节省电源费用,亏大了。。。 状态转移详见代码 #include #include #include using namespace std; const int maxn = 1010; struct lamp { int v,k,c,l; }a[maxn]; int n,v1,k1,c1,l1; int s[maxn]; int d[maxn]; bool cmp(lamp a1,lamp a2) { return a1.v