1326. Bottle Taps-白红宇

1326. Bottle Taps

阅读量：5075 次

发布时间：2019-06-12

本文共 690 字，大约阅读时间需要 2 分钟。

状态压缩DP

题目大意：

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

求最优买法.

思路：

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

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

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

代码及其注释：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define LL long longconst 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<

转载于:https://www.cnblogs.com/liulangye/archive/2012/10/05/2712190.html

你可能感兴趣的文章