day 33 状态压缩dp

二维状态压缩dp

对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等

回路计数

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼

（即走一条哈密尔顿回路）

可看做：从第一栋开始到 遍历完其他的所有方案数

状态压缩从第0位开始，因此在初始化邻接矩阵时要转换一下

#include <bits/stdc++.h>
using namespace std; long long a[22][22], dp[1 << 22][22], ans;
//dp[i][j]:i种状态，走到教学楼j的方案数 (数组稍微开大一点)
int main()
{for(int i = 1; i <= 21; i++)for(int j = 1; j <= 21; j++)if(__gcd(i, j) == 1) a[i - 1][j - 1] = a[j - 1][i - 1] = 1;//从第0位开始 dp[1][0] = dp[0][1] = 1;//2楼到1楼 // 共2^21-1(即全1)种状态 for(int i = 1; i <= (1 << 21) - 1; i++){//考察状态i for(int j = 0; j < 21; j++){//走到教学楼j if(! (i >> j & 1)) continue; //如果状态i不经过教学楼jfor(int k = 0; k < 21; k++){if((i >> k & 1) || ! a[j][k])continue;//如果状态i已经过k或者楼jk之间无路//从新状态i+1<<k,到楼k的方案数 = i到k + i到j到k dp[i + (1 << k)][k] += dp[i][j]; } }}for(int i = 0; i < 21; i++)ans += dp[(1 << 21) - 1][i];//全1状态，最后一次经过i楼，然后最后回到1楼(因为1与所有数互质所以一定有路) cout << ans << endl; return 0;
}

吃奶酪

房间里放着 n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

固定起点（0， 0），遍历，最短路径

memset(a, 127, sizeof(a))

https://www.cnblogs.com/ljysy/p/12535388.html

https://blog.51cto.com/u_3044148/4005292

#include <bits/stdc++.h>
using namespace std;double x[20], y[20], dp[20][(1 << 15) + 15];
int n;
double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
} 
int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];memset(dp, 127, sizeof(dp));//设置各状态距离 for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)//状态:在i点直接到j距离dp[i][j] dp[i][j] = dp[j][i] = dis(i, j); for(int i = 1; i < (1 << n); i++){//遍历所有状态 for(int j = 1; j <= n; j++){ if(! (1 & (i >> (j - 1)))) continue;//不过第j块奶酪 //if(! (i & (1 << (j - 1)))) continue; //相当于上面 for(int k = 1; k <= n; k++){ if(k == j || !(1 & (i >> (k - 1)))) continue;//与j同或该状态不过第k块 dp[j][i] = min(dp[j][i], dp[k][i - (1 << (j - 1))] + dis(j, k));//i-k-j }     }} double ans = 1e9;for(int i = 1; i <= n; i++)ans = min(ans, dp[i][(1 << n) - 1] + dis(i, 0));//从(0,0)开始 printf("%.2lf\n", ans);return 0;
}

郊区春游

#include <bits/stdc++.h>
using namespace std; int n, m, r, vis[205], dis[205][205], edge[20][20], dp[205][(1 << 15) + 15]; 
int main()
{memset(dp, 127, sizeof(dp));cin >> n >> m >> r;for(int i = 1; i <= r; i++) cin >> vis[i];for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dis[i][j] = 1e9;//从i到j最短距离初始化（无穷大：ij间没有路） int a, b, c;for(int i = 0; i < m; i++){cin >> a >> b >> c;dis[a][b] = dis[b][a] = c;//有路}//floyd求i到j最短距离for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(dis[i][j] > dis[i][k] + dis[k][j])dis[i][j] = dis[i][k] + dis[k][j];}}} //把点转化为 1 2 3 4 ... r：问题变为从固定点走，经过每个点过一次距离最短多少？for(int i = 1; i <= r; i++)for(int j = 1; j <= r; j++)edge[i][j] = dis[vis[i]][vis[j]];// tsp状态压缩dpfor(int i = 1; i < (1 << r); i++){for(int j = 1; j <= r; j++){//状态为i时走到点j if(!(i & (1 << (j - 1)))) continue;//状态i不过点jif(i == (1 << (j - 1))){ dp[j][i] = dp[i][j] = 0;continue;}//起点 for(int k = 1; k <= r; k++){//不过j，从k到j if(dp[j][i] > dp[k][i - (1 << (j - 1))] + edge[j][k])dp[j][i] = dp[k][i - (1 << (j - 1))] + edge[j][k];}} }int ans = 1e9;for(int i = 1; i <= r; i++)ans = min(ans, dp[i][(1 << r) - 1]);cout << ans << endl; return 0;
}

一维状态压缩dp

[蓝桥杯 2019 省 A] 糖果

总共m种糖果，状态有2^m - 1种情况

#include <bits/stdc++.h>
using namespace std; int n, m, k, tt, t, a[105], dp[1 << 20]; 
int main()
{cin >> n >> m >> k;memset(dp, -1, sizeof(dp)); //买不到全部则输出-1 for(int i = 0; i < n; i++){tt = 0;for(int j = 0; j < k; j++){cin >> t;tt = tt | (1 << (t - 1)); //二进制表示第i包糖果中有哪几种糖果 }a[i] = tt, dp[tt] = 1;//状态tt最少需1包 }for(int i = 0; i < n; i++){for(int j = 0; j < (1 << m); j++){if(dp[j] == -1) continue;//没有该组合(状态)else if(dp[j | a[i]] == -1) dp[j | a[i]] = dp[j] + dp[a[i]];//新状态无记录 else dp[j | a[i]] = min(dp[j | a[i]], dp[j] + dp[a[i]]); //有记录，记录最小的 }}cout << dp[(1 << m) - 1] << endl;//输出买到所有糖果的最少包数 return 0;
}