1326. Bottle Taps 夜

http://acm.timus.ru/problem.aspx?space=1&num=1326

状态压缩DP  

题目大意：

要买某几种 tap  每种买一个  既可以单个买 也可以成套买 

求最优买法.

思路：

dp[i] 表示 i 状态下的最优买法 即最少的花钱

先初始化 dp[i] 求出单个买的花费

再用成套的买法进行优化   选取符合要求的最优值

代码及其注释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<algorithm>

using namespace std;

#define LL long long

const int INF=0x5fffffff;
const int N=105;
const int M=(1<<20);
int pay[N];// 每种 tap 的单买花费
struct node
{
    int price,k;
}mem[N];//成套的价格 和 代表状态
int dp[M];//最优
int n;
void dfs(int x,int k,int p)//单买花费
{
    if(x==n)
    {
        dp[k]=p;
        return ;
    }
    dfs(x+1,k,p);
    dfs(x+1,k|(1<<x),p+pay[x]);
}
int main()
{
    //freopen("data.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        int m=1<<n;
        for(int i=0;i<n;++i)
        scanf("%d",&pay[i]);
        dfs(0,0,0);
        int k;
        int w,temp;
        scanf("%d",&k);
        for(int i=0;i<k;++i)
        {
            scanf("%d",&mem[i].price);
            scanf("%d",&w);
            mem[i].k=0;
            while(w--)
            {
                scanf("%d",&temp);
                --temp;
                mem[i].k=(mem[i].k|(1<<temp));
            }
        }
        int target=0;
        scanf("%d",&w);
        while(w--)
        {
            scanf("%d",&temp);
            --temp;
            target=(target|(1<<temp));
        }
        int ans=INF;
        for(int i=0;i<m;++i)
        {
            if((i&target)==target)
            ans=min(ans,dp[i]);//求最优
            for(int j=0;j<k;++j)
            {
                dp[(i|mem[j].k)]=min(dp[(i|mem[j].k)],dp[i]+mem[j].price);//更新
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}