The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

9.20上海东华赛区网络赛H题 health (Dp+Dfs+Bit Operation)

Health

 

Unfortunately YY gets ill, but he does not want to go to hospital. His girlfriend LMY gives him N kinds of medicine, which may be helpful. It is not a good idea to take all of them, since taking several different kinds of medicine may cause undesirable side effects. Formally speaking, for each subset S of the N kinds of medicine (excluding the empty set), it has a health value v(S). If YY chooses to take a combination T of the medicines, the final effect to his illness is the sum of health values of all non-empty subsets of T.

YY wants to get healthy as quickly as possible, so the final effect of the medicines he takes should be as great as possible. Of course, YY may choose to take nothing, thus having a zero final effect, if he is too unlucky that all other alternatives he can get are negative…

 

Input

 Input contains multiple test cases.

For each test case, the first line contains a positive integer N (N16), the number of different kinds of medicine YY received from LMY.

The second line contains a single integer M (0M2N).

M lines follow, representing a list of health values.

Each of the M lines contains 2 integers, s (1s<2N) and v (-10000≤v≤10000), indicating a subset of the N kinds of medicine and its health value. Write s in binary representation and add leading zeros if needed to make it exactly N binary digits. If the ith binary digit of s is 1, then the subset it represents includes the ith kind of medicine; otherwise it does not.

It is guaranteed that no two lines of the list describe the same subset. All non-empty subsets that do not appear in the list have health value 0.

Input ends with N=0.

 

Output

 

For each test case, output one line with only one integer, the maximum final effect that can be achieved.

 

Sample Input

2

3

1 10

2 -1

3 100

0

 Sample Output

 109





比赛的时候,看到这道题过的人很多,但是自己却没什么思路,非常郁闷,一看题就知道肯定是个DP,可是究竟怎么动态规划呢?想了半天也想不出来,一直卡在这个题上,后来有个同学提示了我方法,这才明白过来,原来这里面还有位运算,看来我平时缺少位运算方面的训练了。。。哎 我还是太水。。。
分析:这个题的DP思想是把所有1 to 2^n-1的状态所对应的健康值都算出来,然后再其中取一个最大值。我们看看他是如何状态转移的:
            假设 n=3  现在考虑 1 1 1(7,从左到右分别是第3,2,1种药品) 这种状态,如果第三种药品不使用,那么相当于0 1 1 产生的 总健康值;
            这个健康值已经由它的子结构得到。
            如果使用第三种药品,那么我们进行一次DFS,将他对应的所有的有效状态(无效状态对应为0即可)对应的健康值加起来,这样就得到了
            使用第三种药物的总健康值。
            我们将上述子结构和DFS得到的结果相加,便得到了当前状态下的总健康值。
我们做一个循环,i from 1to 2^n-1 ,把所有情况对应的健康值算出来,然后再其中取一个最大值即可。(位运算很重要!)

#include<iostream>
using namespace std;
#define MAX (1<<17)

int value[MAX];
int dp[MAX];
int bin[20];
int n,m;
int sum;
int ans;

void dfs(int i,int p)
{

    
if(i<0)
    
{
        sum
+=value[p];
        
return ;
    }

    
else if(bin[i]==1)
        dfs(i
-1,p+(1<<i));
    dfs(i
-1,p);
}



void solve(int n)
{
    
int now=( (1<<n)-1 );
    
int i;
    
int j=1;
    
int k=-1;
    
for(i=1;i<=now;i++)
    
{
        sum
=0;
        memset(bin,
0,sizeof(bin));
        j
=1;
        k
=-1;
        
while(j*2<=i)
        
{

            
if(j&&i)
            
{
                k
++;
                bin[k]
=1;
            }

            
else 
            
{
                k
++;
                bin[k]
=0;
            }

            j
*=2;

        }

        dfs(k,j);
        dp[i]
=dp[i-j]+sum;
        
if(dp[i]>ans)
        ans
=dp[i];
    }



}



int main()
{
    
int i;
    
while(scanf("%d",&n))
    
{
        ans
=0;
        memset(value,
0,sizeof(value));
        
if(n==0)
            
break;
        scanf(
"%d",&m);
        
for(i=1;i<=m;i++)
        
{

            
int a,b;
            scanf(
"%d%d",&a,&b);
            value[a]
=b;
        }

        solve(n);
        printf(
"%d\n",ans);

    }

    
return 0;
}






做了这个题,突然想起了将10进制转化成2进制的方法,不断模除2,取余数,但是一直没有深究,今天终于明白了,原来如果把这个十进制数考虑成2进制,右移一位相当于除以2,模除2就是把最后那一位给取出来了,不断的模除2,就把这个2进制数一位一位的取出。
PS :感谢那位提示我思路的同学

posted on 2009-09-21 14:28 abilitytao 阅读(1213) 评论(4)  编辑 收藏 引用

评论

# re: 9.20上海东华赛区网络赛H题 health (Dp+Dfs+Bit Operation) 2009-09-21 15:48 OwnWaterloo

> 原来如果把这个十进制数考虑成2进制
在C/C++中,整数本来就是按2进制而不是按10进制存储的。
不存在考虑成2进制的说法。

> 突然想起了将10进制转化成2进制的方法
10进制是表象, 2进制才是本质。
10进制只存在于输入输出的过程中, 变量最终是按2进制存储。



> 右移一位相当于除以2,模除2就是把最后那一位给取出来了
> 不断的模除2,就把这个2进制数一位一位的取出。
int i,d;
d = i % 2u;
i /= 2u;

如果你使用的编译器不是古董,第2、3行代码也会分别被编译为位与、移位—— 不一定真的需要写为 & , >>= —— 而不是除法。

  回复  更多评论   

# re: 9.20上海东华赛区网络赛H题 health (Dp+Dfs+Bit Operation) 2009-09-21 19:08 abilitytao

@OwnWaterloo
呵呵 谢谢指点 学习了^_^  回复  更多评论   

# re: 9.20上海东华赛区网络赛H题 health (Dp+Dfs+Bit Operation) 2009-09-21 19:47 qwe

当时也想到了 , 因为这复杂度没敢写!LZ你能分析下这复杂度吗?  回复  更多评论   

# re: 9.20上海东华赛区网络赛H题 health (Dp+Dfs+Bit Operation) 2009-09-30 18:09 abilitytao

@qwe
最低2^16 最高2^32
折中一下 似乎可以接受 对了 请问你有更好的方法吗?   回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理