东莞做营销型网站,网站后台更新内容后,12306网站开发成本,天猫购物商城官网二维状态压缩dp对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等回路计数小蓝现在在第一栋教学楼#xff0c;他想要访问每栋教学楼正好一次#xff0c;最终回到第一栋教学楼#xff08;即走一条哈密尔顿回路#xff09;可看做#xff1…二维状态压缩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之间无路//从新状态i1k,到楼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.htmlhttps://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;
}
