# 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

假设 n=3  现在考虑 1 1 1(7，从左到右分别是第3，2，1种药品) 这种状态，如果第三种药品不使用，那么相当于0 1 1 产生的 总健康值；
这个健康值已经由它的子结构得到。
如果使用第三种药品，那么我们进行一次DFS，将他对应的所有的有效状态（无效状态对应为0即可）对应的健康值加起来，这样就得到了
使用第三种药物的总健康值。
我们将上述子结构和DFS得到的结果相加，便得到了当前状态下的总健康值。

#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;
}

PS :感谢那位提示我思路的同学

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

### 评论

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

> 原来如果把这个十进制数考虑成2进制

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

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

回复  更多评论

@OwnWaterloo

@qwe