POJ 2184 Cow Exhibition(变形01背包)_y - cow exhibition-程序员宅基地

技术标签: 背包dp  POJ  poj  01背包  

题目链接:
POJ 2184 Cow Exhibition
题意:
给n头牛,每头牛有两个属性:smart和fun,选出若干头牛使得这些牛的smart和fun之和最大,并且smart和与fun和均不为负。
每头牛的smart和fun可以为负。
分析:
01背包和滚动数组。
用dp[j]表示得到smart和为j时的fun和最大值。但是因为j可能为负,一开始我是用map,但是一直TLE。。。
后来改成二维表示:dp[j][0]:smart和为j(j>0)时的最大fun和,dp[j][1]:smart和为-j(j<0)时的最大fun和
初始化:
dp为最小,但是dp[0][0]=dp[0][1]=0;
状态转移方程需要注意要根据smart[i]的正负确定遍历的顺序,而且还要考虑j-smart[i]的正负。
最后再遍历扫一下dp[j][0]取最大就好了。

//600K 47MS
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_N=110;
const int MAX_M=110000;
const int inf=INT_MIN/3;

int n;
int smart[MAX_N],fun[MAX_N],dp[MAX_M][2];

int main()
{
    //freopen("Lin.txt","r",stdin);
    //freopen("Lout.txt","w",stdout);
    while(~scanf("%d",&n)){
        int max_sum=0,min_sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&smart[i],&fun[i]);
            if(smart[i]>0) max_sum+=smart[i];
            else min_sum+=smart[i];
        }
        for(int j=1;j<=max(abs(min_sum),abs(max_sum))+1100;j++){
            dp[j][0]=dp[j][1]=inf;
        }
        dp[0][0]=dp[0][1]=0;
        for(int i=1;i<=n;i++){
            if(smart[i]>=0){
                for(int j=max_sum;j>=0;j--){
                    if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[j][0]=max(dp[-(j-smart[i])][1]+fun[i],dp[j][0]);
                    else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[j][0]=max(dp[j-smart[i]][0]+fun[i],dp[j][0]);
                    //printf("i=%d j=%d dp[abs(j)][0]=%d\n",i,j,dp[abs(j)][0]);
                }
                for(int j=0;j>=min_sum;j--){
                    if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[-j][1]=max(dp[-(j-smart[i])][1]+fun[i],dp[-j][1]);
                    else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[-j][1]=max(dp[j-smart[i]][0]+fun[i],dp[-j][1]);
                    //printf("i=%d j=%d dp[abs(j)][1]=%d\n",i,j,dp[abs(j)][1]);
                }
            }else {
                for(int j=min_sum;j<=0;j++){
                    if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[-j][1]=max(dp[-(j-smart[i])][1]+fun[i],dp[-j][1]);
                    else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[-j][1]=max(dp[j-smart[i]][0]+fun[i],dp[-j][1]);
                    //printf("i=%d j=%d dp[abs(j)][1]=%d\n",i,j,dp[abs(j)][1]);
                }
                for(int j=0;j<=max_sum;j++){
                    if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[j][0]=max(dp[-(j-smart[i])][1]+fun[i],dp[j][0]);
                    else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[j][0]=max(dp[j-smart[i]][0]+fun[i],dp[j][0]);
                    //printf("i=%d j=%d dp[abs(j)][0]=%d\n",i,j,dp[abs(j)][0]);
                }
            }
        }
        int ans=0;
        for(int i=max_sum;i>=0;i--){
            if(dp[i][0]>=0){
                ans=max(ans,i+dp[i][0]);
                //printf("i=%d dp[i][0]=%d\n",i,dp[i][0]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ramay7/article/details/51143356

智能推荐

PostgreSQL 之 流复制概述_postgresql数据库的同步流复制-程序员宅基地

文章浏览阅读5.9k次,点赞5次,收藏10次。基于流复制协议的wal日志从主节点到备节点实时复制传输与复用。为了实现数据库的高可用,一般需要搭建主库和备库。流复制是搭建主备库的一种有效方式,它不需要额外增加软件,只需要在单数据库模式的基础上,再复制一份PostgreSQL数据库到另外的一台机器上,对两台数据库进行参数配置,即可实现。这两套数据库之间的数据,通过wal日志,后台自动同步。对外部的应用程序而言,可以看作是两套数据库,需要根_postgresql数据库的同步流复制

PHPExcel的自定义导出及合并单元格_php excel导出 合并单元格-程序员宅基地

文章浏览阅读1.1w次。首先自定义导出,我用的是一个下拉多选框的一个插件,百度一下就可找到,为了样式好看。如图value值对应的是你数据库中查出的字段值,text对应的是你的表头信息。ok,然后我是通过GET把这俩个值传到我们控制器的。引入导出类,这个就不多说。然后就是查询数据库,把数据处理成一个二维数组,进行循环遍历输出在表格中我的数据格式是1对多的关系,一个班主任对应多个班级,那么我要在表格中合并这个班主任,$cou..._php excel导出 合并单元格

概率论基础 - 6 - 切比雪夫不等式-程序员宅基地

文章浏览阅读8.2k次。切比雪夫不等式可以使人们在随机变量X的分布未知的情况下,对事件$|X-\mu|<\varepsilon $ 概率作出估计。定义假设随机变量XXX具有期望E(X)=μE(X)=\muE(X)=μ, 方差 Var(X)=σ2Var(X)=\sigma^2Var(X)=σ2,则对于任意正数ε\varepsilonε ,有不等式成立:P{∣X−μ∣≥ε}≤σ2ε2\mathbb P\{|X-\mu| \geq \varepsilon\} \leq \frac{\sigma^{2}}{\var._切比雪夫不等式

关于Rviz的一些问题_fixed frame unknown frame map-程序员宅基地

文章浏览阅读4k次。ROS No transform from [sth] to [sth]Like this:No transform from [right_leg] to [base_link]参考RViz keep saying "No transform from [front_left] to [base_link]"提到:I got it! It took me a whole day to ..._fixed frame unknown frame map

spark机器学习-常见函数使用(pyspark版)_pyspark linearinterpolator函数-程序员宅基地

文章浏览阅读220次。参考spark机器学习 基于pycharm进行开发,pyspark安装见上篇博文 数据集包含的字段为:id,年龄,性别,职业,邮编from pyspark import SparkContext,SparkConf#conf = SparkConf().setAppName("test").setMaster("local")sc = SparkContext(conf=conf)..._pyspark linearinterpolator函数

vue兼容IE11_vue2.7 兼容ie11-程序员宅基地

文章浏览阅读2.3k次。三个步骤1.package.json -&gt; dependencies增加"babel-polyfill": "^6.26.0"(版本号可以根据npm install --save babel-polyfill拿到)2.main.js -&gt; 增加import "babel-polyfill"3.index.js -&gt; 增加import "babel-p..._vue2.7 兼容ie11

随便推点

在WinForm中增加查询对话框对DataGridView数据进行循环查找-程序员宅基地

文章浏览阅读441次。在开发WinForm窗体程序时,我们希望增加一个对DataGridView数据进行查找的对话框,类似于Visual Studio中的“查找和替换”对话框,但是功能没有这么复杂,需求如下:  1. 用户可以通过主窗体中的菜单打开数据查找对话框。  2. DataGridView数据未加载前不显示查找对话框。  3. 查找对话框中可以进行大小写匹配和全..._winform datagridview 查询输入框

MySQL执行外部sql脚本文件的命令及sql脚本的基本写法_执行sql脚本文件的命令是什么-程序员宅基地

文章浏览阅读6.4w次,点赞18次,收藏81次。最近重新踩了一下mysql 这边的坑,记录一下自己忽略的地方~~sql脚本是包含一到多个sql命令的sql语句,将这些sql脚本放在一个文件中,然后通过相关的命令执行这个sql脚本文件。SQL脚本可用于插入数据,读取数据,更新数据,和删除数据。它们也可以用于创建数据库对象,如表,视图,存储过程,他们甚至可以用于创建整个数据库本身 - 完整的表,数据,用户,等等。1、编写sql脚本..._执行sql脚本文件的命令是什么

Clion-如何切换Debug与Release版本_clion debug 改 release-程序员宅基地

文章浏览阅读1w次,点赞8次,收藏3次。综述最近在cgal吃够了苦头,在debug模式下,各种cgal error得到老师指点,说是在release模式下会好很多。 所以研究了一下如何从debug到release步骤点击Preference 依次选择: Build,Execution,Deployment 点击左侧的框,“+”,添加新的模式。 系统一般会自动给你产生release版本。 然..._clion debug 改 release

【Numpy】中np.random.uniform()函数用法-程序员宅基地

文章浏览阅读3.7w次,点赞35次,收藏118次。参考: https://www.cnblogs.com/fpzs/p/10504658.htmlnumpy.random.uniform()介绍:函数原型: numpy.random.uniform(low,high,size)功能:从一个均匀分布[low,high)中随机采样,注意定义域是左闭右开,即包含low,不包含high.参数介绍:low: 采样下界,float类型,默认值为0;high: 采样上界,float类型,默认值为1;size: 输出样本数目,为int或元组(t._np.random.uniform

phpMyAdmin下载-程序员宅基地

文章浏览阅读196次。下载地址:网盘下载phpMyAdmin 是一个以PHP为基础,以Web-Base方式架构在网站主机上的MySQL的数据库管理工具,让管理者可用Web接口管理MySQL数据库。借由此Web接口可以成为一个简易方式输入繁杂SQL语法的较佳途径,尤其要处理大量资料的汇入及汇出更为方便。其中一个更大的优势在于由于phpMyAdmin跟其他PHP程式一样在网页服务器上执行..._phpmyadmin war包下载

eplan导出部件汇总表_小技巧如何将EPLAN表格导出到EXCEL-程序员宅基地

文章浏览阅读9.2k次,点赞4次,收藏10次。编辑丨钻石海出品丨电气CAD论坛在用EPLAN出材料汇总表时,默认是在软件环境下表现的,即便可以导出成PDF文档交付到采购部门,但也不如xls格式的要方便,因为其它部门可能要导入到ERP或统计、运算数量等操作,EPLAN其实可以通过“标签”功能来导出汇总表,接下来我们就来看看如何操作:第一步:EXCEL新建文档表头格式:#H#填充内容:###不用在意符号,按自己要求做好模板,并在需要填充..._eplan导出标签 表头设计

推荐文章

热门文章

相关标签