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

2019-07-14 00:32发布

本题难处好像是在于 能够把一些灯泡换成电压更高的灯泡以节省电源的钱 。所以也才有了对最优方案的探求 好的处理方法是依照电压从小到大排序。仅仅能让前面的换成后面的。也就满足了把一些灯泡换成电压更高的灯泡 的要求; 一种电压的灯泡,要么不换。要换则应该全换:换。说明用当前的电源不值;而既然不值则应该所有换掉以避免使用当前电源,不然即添加了灯泡费用又没节省电源费用,亏大了。。。 状态转移详见代码 #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