首页 > 代码库 > uva 11400 - Lighting System Design(动态规划 最长上升子序列问题变型)
uva 11400 - Lighting System Design(动态规划 最长上升子序列问题变型)
本题难处好像是在于 可以把一些灯泡换成电压更高的灯泡以节省电源的钱 ,所以也才有了对最优方案的探求
好的处理方法是按照电压从小到大排序,只能让前面的换成后面的,也就满足了把一些灯泡换成电压更高的灯泡的要求;
一种电压的灯泡,要么不换,要换则应该全换:换,说明用当前的电源不值;而既然不值则应该全部换掉以避免使用当前电源,不然即增加了灯泡费用又没节省电源费用,亏大了。。。
状态转移详见代码
#include<cstdio> #include<cstring> #include<algorithm> 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<a2.v; } int main() { while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(s,0,sizeof(s)); memset(d,0,sizeof(d)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&v1,&k1,&c1,&l1); a[i].v=v1; a[i].k=k1; a[i].c=c1; a[i].l=l1; } sort(a+1,a+n+1,cmp); s[0]=0; for(int i=1;i<=n;i++) { s[i]=s[i-1]+a[i].l; } d[0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) { if(j==-0) d[i]=(s[i])*a[i].c+a[i].k; else d[i]=min(d[j]+(s[i]-s[j])*a[i].c+a[i].k,d[i]); } } printf("%d\n",d[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。