注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2184Cow Exhibition题解  

2014-03-14 20:31:25|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                               奶牛展览
                                                     BY   LGS
题目大意;有n头奶牛,每个奶牛有两个值:A,B。要在其中选择任意个奶牛,使所有A和B的和最大,且所有A的值要>0,所有B的值要>0;

题解:很明显的背包,只要稍稍变变。可以用滚动数组记录F[2][300010]下的A+B最优值,150000为0,以下为负数,以上为正数。输出的时候只需要判断F值-i+150000是否大于=0即可,i从150000到250000循环。注意啊,细节:一开始赋初值时一定要开-INF,不能开-1.由于我写背包惯性,直接将F[I][J]弄成-1了,导致wa了好几次都没A,最后在讨论里发现有个和我一样的人。。。

总结:水背包。细节
代码:
#include<cstdio>
#include<cstring>
#define INF 999999999;
using namespace std;
int i,j,k,n,tt,ans;
int f[2][400010],a[200],b[200],c[200];
int max(int a,int b){return (a>b)?a:b;}
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++)
     {scanf("%d%d",&a[i],&b[i]);c[i]=a[i]+b[i];}
for (i=0;i<=1;i++)
 for (j=0;j<=400000;j++) f[i][j]=-INF;

f[0][150000]=0;tt=1;
for (i=1;i<=n;i++){
   for (j=30000;j<=280000;j++){
       if (f[1-tt][j]!=-1){
   f[tt][j+a[i]]=max(f[1-tt][j]+c[i],f[tt][j+a[i]]);
   f[tt][j]=max(f[tt][j],f[1-tt][j]);
                          }              
                               }
                   tt=1-tt;
                   }
          tt=1-tt;ans=0;
for (i=150000;i<=280000;i++) if (f[tt][i]-(i-150000)>=0)
          ans=max(ans,f[tt][i]);
printf("%d\n",ans);
return 0;
}
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018