当前位置: 代码迷 >> 综合 >> pku 2148 Cow Exhibition
  详细解决方案

pku 2148 Cow Exhibition

热度:70   发布时间:2023-12-21 05:15:03.0

2184 Cow Exhibition 0-1背包问题变形,选定一个值作状态后,另一值可被标识。如果有更多信息需记录(信息量-1)的数组应该可以的。http://acm.pku.edu.cn/JudgeOnline/problem?id=1717 Dominos这道题也是一道类似的题目,
还可以用搜索来做。把有利的值统统加入,同时记下可能使不符合的元素,做一次排除,找到正确的最优值。 

0-1背包有时(分堆)可以用随机贪心来做的,大致思路是从多的一堆中随机一个放入少的一堆中。

 

#include  < iostream >
#define  N 101
using   namespace  std;

int  f[N],s[N];
int  n,num;
int  total;
int  tF,tS;

int  findProper( int  a, int  b, int  idx)
{
    
if  (a >= 0   &&  b >= 0 )
    {
        
if  (a  +  b  > total)
            total 
=  a  +  b;
        
return  a + b;
    }
    
if  (idx >= num  ||  a  +  b  <  total)
        
return   0 ;
    
int  i  =  findProper(a,b,idx + 1 );
    
int  j  =  findProper(a + f[idx],b + s[idx],idx + 1 );
    
return  max(i,j);
}

int  main()
{
    
int  i;
    scanf(
" %d " , & n);
    total 
=  tF  =  tS  =  num  =   0 ;

    
int  a,b;
    
for  (i = 0 ; i < n;  ++ i)
    {
        scanf(
" %d%d " , & a, & b);

        
if  (a >= 0   &&  b >= 0 )
        {
            total 
+=  a + b;
            tF 
+=  a;
            tS 
+=  b;
        }
        
else   if  (a  *  b  <= 0 )
        {
            
if (a  +  b  >   0 )
            {
                tF 
+=  a;
                tS 
+=  b;
                a 
=   - a;
                b 
=   - b;
            }
            f[num]
= a;
            s[num]
= b;
            
++ num;
        }
    }
    printf(
" %d " ,findProper(tF,tS, 0 ));
}