首页 技术 正文
技术 2022年11月23日
0 收藏 538 点赞 2,785 浏览 752 个字

题目中有一个重要的信息是:每一种灯泡只能换成比它电压更大的灯泡,因此电压的大小限制了状态的转移。因此,在这里按照电压从小到大把每种灯泡排序,使得在考虑后面的灯泡时,前面的灯泡自然可以换成后面的灯泡。状态转移方程为\(dp[i]=max(dp[j]+(s[i]-s[j])*c[i]+k[i]),j\in[0,i-1]​\),s[i] 表示前 i 种灯泡的数量。

代码如下:

#include <bits/stdc++.h>
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1010;int n,dp[maxn],s[maxn];
struct node{
int volt,src,cost,num;
}l[maxn];bool cmp(const node& x,const node& y){
return x.volt<y.volt;
}
void init(){
cls(dp,0x3f);cls(l,0);cls(s,0);
}int main(){
while(scanf("%d",&n)&&n){
init();
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&l[i].volt,&l[i].src,&l[i].cost,&l[i].num);dp[0]=0;
sort(l+1,l+n+1,cmp);for(int i=1;i<=n;i++)
s[i]=s[i-1]+l[i].num;for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*l[i].cost+l[i].src);printf("%d\n",dp[n]);
}
return 0;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102