UVA 11691 - Allergy Test(状压dp+贪心) - c++编程基础

题目链接：11691 - Allergy Test

题意：这题题意看了老半天都没弄懂，好在后面找到个PPT，上面有中文题意- -，不过上面的做法是纯贪心，挺巧妙的但是感觉有点不靠谱，下载地址：http://par.cse.nsysu.edu.tw/~advprog/advprog2011/11691.ppt N 敏原的存活期，每天可把一敏原注入人。若有以上敏原存活於人中，法行 (也就是每敏原都必有一天是存活於人中)。束於最後的敏原死亡的那天，求最短天。思路：我的思路是状态压缩dp+贪心，20个过敏原做状态压缩，然后每次加过敏原的时候，尽量往里面覆盖，dp[s][k]，s表示过敏原使用状态，k表示后面通出来单独存在过敏原的天数，然后选一个新的过敏原去尽量覆盖他，这样k的一维只要开到7就够了，因为每段长度最多就是7。状态转移方程为： dp[k][s] = min{dfs(s^(1< 代码：

#include 
   
    
#include 
    
      #include 
      #include 
      
        using namespace std; #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b) (a):(b)) #define max(a,b) ((a)>(b) (a):(b)) const int N = 25; const int M = (1<<20) + 5; int t, n, num[N], dp[M][8]; int dfs(int s, int k) { if (dp[s][k] != -1) return dp[s][k]; dp[s][k] = INF; if (s == (1<