首页 > 代码库 > HDU 3217 Health（状压DP)

HDU 3217 Health（状压DP)

2024-07-25 20:38:32   223人阅读

Problem Description
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 have side effect. 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 be healthy as quickly as possible, so the final effect of the medicines he takes should be as large as possible. Of course, YY may choose taking nothing to have a zero final effect, if he is too unlucky to achieve a positive one…
 

Input
Input contains multiple test cases.

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

The second line contains a single integer M (0≤M≤2N).

M lines follow, representing a list of health values.

Each of the M lines contains 2 integers, s (1≤s<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
 

Source
2009 Shanghai Network Contest Host by DHU

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
typedef long long LL;
using namespace std;
int dp[17][1<<17];
int n,m;

int main()
{
    int s,u,v;
    while(~scanf("%d",&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&m);
        int s=(1<<n)-1;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            dp[0][u]=v;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=s;j++)
            {
                if(j&(1<<(i-1)))
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-(1<<(i-1))];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        int ans=-INT_MAX;
        for(int i=0;i<=s;i++)
            ans=max(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

HDU 3217 Health（状压DP)


联系
我们