Vijos 1456 最小总代价（状压dp）

Love The Way You Lie 2021-12-22 11:01 216阅读 0赞

看到这道题n只有16，就可以想到状压dp

每个人只有经过或者没经过，那就用1表示经过，0表示没经过

但是不是当前在谁那里，所以再加一维来记录

所以f\[state\]\[i\]表示在物品在i，当前的状态是state情况下的最小总代价

有几个细节要注意

（1）刷表法。要提前初始化为-1，然后然后每个起点为0.。做的时候要判断当前状态存不存在。

（2）之前状态存在，当前这个人不存在才可以去做。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define REP(i, a, b) for(int i = (a); i < (b); i++)
    #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    using namespace std;
    
    const int MAXN = 20;
    int g[MAXN][MAXN], f[(1<<16)+10][MAXN], n;
    
    int main()
    {
    	scanf("%d", &n);
    	REP(i, 0, n)
    		REP(j, 0, n)
    			scanf("%d", &g[i][j]);
    	
    	memset(f, -1, sizeof(f));
    	REP(i, 0, n) f[1<<i][i] = 0;
    	
    	int ans = 1e9;
    	REP(i, 0, 1 << n)
    		REP(j, 0, n)
    			if(f[i][j] != -1)
    				REP(k, 0, n)
    					if(!(i & (1 << k)))
    					{
    						int& state = f[i | (1 << k)][k];
    						if(state == -1) state = f[i][j] + g[j][k];
    						else state = min(state, f[i][j] + g[j][k]);
    						if((i | (1 << k)) == ((1 << n) - 1)) ans = min(ans, state);
    					}
    	printf("%d\n", ans);
    	
    	return 0;
    }

转载于:https://www.cnblogs.com/sugewud/p/9819334.html

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】Most Powerful

[E-Most Powerful\_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)][E-Most Powerful_dp_ _nowcoder.com]

以你之姓@/ 2024年03月17日 08:58/ 0 赞/ 72 阅读

相关【状压DP】简单环

怎么办，感觉现在所谓会的算法都是云的以为自己会，然后随便出一道题就不会云玩家是吧好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好

柔情只为你懂/ 2024年03月17日 08:57/ 0 赞/ 58 阅读

相关 group 状压dp

　　应某些人要求，我把标签删掉了　　这是一道好题。　　一看$c<=16$果断状压，但是怎么压？　　一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c

逃离我推掉我的手/ 2023年08月17日 16:48/ 0 赞/ 138 阅读

相关 Woj 1608 - Calculation 状压dp

思路来自于武大的一个大神并不是我的。。。题目链接：[http://acm.whu.edu.cn/land/problem/detail?problem\_id=1608&

柔情只为你懂/ 2022年08月21日 14:59/ 0 赞/ 197 阅读

相关 HDU3182-状压dp

Hamburger Magi Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

川长思鸟来/ 2022年07月13日 14:56/ 0 赞/ 222 阅读

相关 HDU4114-floyd+ 状压dp

Disney's FastPass Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/327

柔光的暖阳◎/ 2022年07月11日 13:40/ 0 赞/ 232 阅读

相关状压dp（瞎BB）

最近在写状压dp，写得不太顺利啊，抠很久才抠出来。可见如此之菜。状态压缩dp（简称状压dp）是一种非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数

迷南。/ 2022年06月17日 08:13/ 0 赞/ 242 阅读

相关 Vijos 1456 最小总代价（状压dp）

看到这道题n只有16，就可以想到状压dp 每个人只有经过或者没经过，那就用1表示经过，0表示没经过但是不是当前在谁那里，所以再加一维来记录所以f\[state\]\[

Love The Way You Lie/ 2021年12月22日 11:01/ 0 赞/ 217 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 310 阅读

相关 165. 小猫爬山(状压dp)

翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>\_<）。翰翰和达达只好花钱让它们坐索道

悠悠/ 2021年11月10日 09:24/ 0 赞/ 302 阅读