博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ZOJ 1013 Great Equipment(DP)
阅读量:5976 次
发布时间:2019-06-20

本文共 2944 字,大约阅读时间需要 9 分钟。

 题目链接:

采用动态规划解决。

设f[n][x][y] 表示前n辆车装了x个装备1和y个装备2之后能装的最多的装备3的个数。

递推关系如下:

f[n][x][y] = max ( f[n - 1][x - a][y - b] + c);    其中f[0][x][y]=0

 

其中a和b的范围为第n辆车可以装的装备1和装备2的个数, c 为第n辆车装完a个装备1和b个装备2后可以装的装备3的个数。

通过递推求得f[n][x][y]后,可以遍历x和y(x,y的范围可以在上述递推的过程中得到)求得最终的结果。

由于f[n]只和f[n-1]有关,所以实际上 f 数组的第一维只需要2就可以(详见代码)

1 #include
2 #include
3 using namespace std; 4 5 int min(int x ,int y) 6 { 7 return x
y? x:y;13 }14 15 int fun(int x)16 {17 return x>0? x:0;18 }19 int f[2][501][501];20 int main()21 {22 int carNum,w1,s1,d1,w2,s2,d2,w3,s3,d3,c1,c2,c3,d4;23 int limit[101][2];24 25 int count=1;26 cin>>carNum;27 while(carNum)28 {29 cin>>w1>>s1>>d1>>w2>>s2>>d2>>w3>>s3>>d3>>c1>>c2>>c3>>d4;30 for(int i=1;i<=carNum;i++)31 cin>>limit[i][0]>>limit[i][1];32 33 int prev=0,now=1;34 int prev_max1=0,prev_max2=0,temp,n1,n2,n3;35 memset(f[0],0,sizeof(f[0]));36 37 for(int i=1;i<=carNum;i++)38 {39 memset(f[now],-1,sizeof(f[now]));40 n1=min(limit[i][0]/w1,limit[i][1]/s1);41 for(int a=0;a<=n1;a++)42 {43 n2=min( (limit[i][0]-a*w1)/w2, (limit[i][1]-a*s1)/s2 );44 if(a==0)temp=n2;45 for(int b=0;b<=n2;b++)46 {47 n3=min( (limit[i][0]-a*w1-b*w2)/w3, (limit[i][1]-a*s1-b*s2)/s3 );48 for(int h=0;h<=prev_max1;h++)49 for(int k=0;k<=prev_max2;k++)50 {51 if(f[prev][h][k]!=-1)52 f[now][h+a][k+b]=max( f[now][h+a][k+b], f[prev][h][k]+n3 );53 }54 55 }56 }57 prev_max1+=n1;58 prev_max2+=temp;59 60 int pp=prev;61 prev=now;62 now=pp;63 }//for(int i=1;i<=carNum;i++)64 //结束后prev指向的数组存有结果;65 int result=0;66 for(int i=0;i<=prev_max1;i++)67 for(int j=0;j<=prev_max2;j++)68 {69 if(f[prev][i][j]!=-1)70 {71 int groupNum=65535; //max72 if(c1!=0)73 groupNum=min(i/c1,groupNum);74 if(c2!=0)75 groupNum=min(j/c2,groupNum);76 if(c3!=0)77 groupNum=min(groupNum,f[prev][i][j]/c3);78 result=max(result,fun(i-groupNum*c1)*d1+fun(j-groupNum*c2)*d2+fun(f[prev][i][j]-groupNum*c3)*d3+groupNum*d4);79 // 开始没有加fun函数,没有考虑到i-groupNum等小于0;80 }81 }82 if(count>1)cout<
<
>carNum;86 87 }88 89 return 0;90 }

 【版权声明】转载请注明出处 

转载于:https://www.cnblogs.com/TenosDoIt/archive/2013/04/15/3021989.html

你可能感兴趣的文章
poj - 1860 Currency Exchange
查看>>
洛谷 P2486 BZOJ 2243 [SDOI2011]染色
查看>>
数值积分中的辛普森方法及其误差估计
查看>>
Web service (一) 原理和项目开发实战
查看>>
跑带宽度多少合适_跑步机选购跑带要多宽,你的身体早就告诉你了
查看>>
Javascript异步数据的同步处理方法
查看>>
iis6 zencart1.39 伪静态规则
查看>>
SQL Server代理(3/12):代理警报和操作员
查看>>
Linux备份ifcfg-eth0文件导致的网络故障问题
查看>>
2018年尾总结——稳中成长
查看>>
通过jsp请求Servlet来操作HBASE
查看>>
Shell编程基础
查看>>
Shell之Sed常用用法
查看>>
Centos下基于Hadoop安装Spark(分布式)
查看>>
mysql开启binlog
查看>>
设置Eclipse编码方式
查看>>
分布式系统唯一ID生成方案汇总【转】
查看>>
并查集hdu1232
查看>>
Mysql 监视工具
查看>>
Linux Namespace系列(09):利用Namespace创建一个简单可用的容器
查看>>