AcWing 1243. 糖果

原题链接

考察:IDA* or 状压+背包dp

思路一:

       n个物品包,每个都可以用二进制表示,f[i][j]表示前i个物品组成j状态最少需要多少包,状态转移方程为

int t = min(f[i-1][j|candy[i]],f[i-1][j]+1);
                f[i][j|candy[i]] = min(t,f[i][j|candy[i]]);
                f[i][j] = min(f[i-1][j],f[i][j]);//不选第i件       

      但是直接这么写会TLE,这里有一个状态是无用的状态,就是f[i-1][j|candy[i]],这个状态如果!=INF,说明i-1件就已经凑成状态z(z=j|candy[i]),此时两种情况:

1. z==candy[i],毫无疑问此时只选第i件更优
2. z!=candy[i],但是f[i-1][z]!=INF,说明i-1件能凑成z,而i件也能凑成z.f[i-1][j|candy[i]]的效果实际与第三行代码相同.因为j|candy[i]一定也会被遍历到.但是第三行代码是不能省略的.

1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 110,M = 1<<20,INF = 0x3f3f3f3f;
 5 int n,m,k,candy[N],f[2][M+1];
 6 int main()
 7 {
 8     scanf("%d%d%d",&n,&m,&k);
 9     for(int i=1;i<=n;i++)
10       for(int j=1;j<=k;j++)
11       {
12           int x; scanf("%d",&x);
13           candy[i]|=1<<x-1;
14       }
15     memset(f,0x3f,sizeof f);
16     f[0&1][0] = 0;
17     int all = (1<<m)-1;
18     for(int i=1;i<=n;i++)
19       for(int j=0;j<=all;j++)
20       {
21             if(f[i-1&1][j]<=n)
22             {
23               f[i&1][j|candy[i]] = min(f[i&1][j|candy[i]],f[i-1&1][j]+1);
24                 f[i&1][j] = min(f[i-1&1][j],f[i&1][j]);//不选第i件 
25           }
26       }
27     if(f[n&1][all]<=m) printf("%d\n",f[n&1][all]);
28     else printf("-1\n");
29     return 0;
30 }      

状压dp

也可以直接压缩为一维.

思路二:

1. 迭代加深:从小到大枚举可能的答案.如果枚举的答案不符合继续++枚举下一个
2. 估价函数:计算当前状态到目标状态至少还需要几步,如果枚举的答案<估价函数,那么可以直接返回.
3. 每次都选择没有的口味中,有此口味最少的包数的那一列.

1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 25,M = 1<<20;
 7 int logs[M+1],n,m,k,all;
 8 vector<int> v[N];
 9 int lowbit(int x)
10 {
11     return x&-x;
12 }
13 int h(int st)
14 {
15     int res = 0;
16     for(int i=all-st;i;i-=lowbit(i))
17     {
18         int c = logs[lowbit(i)];
19         res++;
20         for(int j=0;j<v[c].size();j++)
21              i&=~v[c][j];
22     }
23     return res;
24 }
25 bool dfs(int dep,int now)
26 {
27     if(!dep||h(now)>dep) return now==all;
28     int t = -1;
29     for(int i=all-now;i;i-=lowbit(i))
30     {
31         int c = logs[lowbit(i)];
32         if(t==-1||v[t].size()>v[c].size()) t = c;
33     }
34     for(int i=0;i<v[t].size();i++)
35        if(dfs(dep-1,now|v[t][i])) return 1;
36     return 0;
37 }
38 int main()
39 {
40     scanf("%d%d%d",&n,&m,&k);
41     all = (1<<m)-1;
42     for(int i=0;i<=20;i++) logs[1<<i] = i;
43     for(int i=1;i<=n;i++)
44     {
45         int st = 0;
46         for(int j=1;j<=k;j++)
47         {
48             int x; scanf("%d",&x);
49             st|=1<<x-1;
50         }
51         for(int j=0;j<m;j++)
52           if(st>>j&1) v[j].push_back(st);
53     }
54     int dep = 1;
55     while(dep<=m&&!dfs(dep,0)) dep++;
56     if(dep>m) puts("-1");
57     else printf("%d\n",dep);
58     return 0;
59 }      

DFS优化