关键词:
之前写了一份此题关于模拟退火的方法,现在来补充一下状压dp的方法。
其实直接在dfs中状压比较好想,而且实现也很简单,但是网上有人说这种方法是错的。。。并不知道哪错了,但是就不写了,找了一个正解。
正解的区别在于状态,(树高是啥意思),每次都是从当前状态的子集转移过来。这里用到了快速枚举子集的操作,很值得写一下。
题干:
题目描述 参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 nnn 个深埋在地下的宝藏屋, 也给出了这 nnn 个宝藏屋之间可供开发的m mm 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远, 也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路 则相对容易很多。 小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。 在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。 新开发一条道路的代价是: L×KmathrmL imes mathrmKL×K L代表这条道路的长度,K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。 请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代 价最小,并输出这个最小值。 输入输出格式 输入格式: 第一行两个用空格分离的正整数 n,mn,mn,m,代表宝藏屋的个数和道路数。 接下来 mmm 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏 屋的编号(编号为 1−n1-n1−n),和这条道路的长度 vvv。 输出格式: 一个正整数,表示最小的总代价。 输入输出样例 输入样例#1: 复制 4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1 输出样例#1: 复制 4 输入样例#2: 复制 4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 2 输出样例#2: 复制 5 说明 【样例解释1】 小明选定让赞助商打通了1 11 号宝藏屋。小明开发了道路 1→21 o 21→2,挖掘了 222 号宝 藏。开发了道路 1→41 o 41→4,挖掘了 444 号宝藏。还开发了道路 4→34 o 34→3,挖掘了3 3 3号宝 藏。工程总代价为:1×1+1×1+1×2=41 imes 1 + 1 imes 1 + 1 imes 2 = 4 1×1+1×1+1×2=4 【样例解释2】 小明选定让赞助商打通了1 11 号宝藏屋。小明开发了道路 1→21 o 21→2,挖掘了 222 号宝 藏。开发了道路 1→31 o 31→3,挖掘了 333 号宝藏。还开发了道路 1→41 o 41→4,挖掘了4 4 4号宝 藏。工程总代价为:1×1+3×1+1×1=51 imes 1 + 3 imes 1 + 1 imes 1 = 51×1+3×1+1×1=5 【数据规模与约定】 对于20% 20\%20%的数据: 保证输入是一棵树,1≤n≤81 le n le 81≤n≤8,v≤5000v le 5000v≤5000 且所有的 vv v都相等。 对于 40%40\%40%的数据: 1≤n≤81 le n le 81≤n≤8,0≤m≤10000 le m le 10000≤m≤1000,v≤5000v le 5000v≤5000 且所有的v v v都相等。 对于70% 70\%70%的数据: 1≤n≤81 le n le 81≤n≤8,0≤m≤10000 le m le 10000≤m≤1000,v≤5000v le 5000v≤5000 对于100% 100\%100%的数据: 1≤n≤121 le n le 121≤n≤12,0≤m≤10000 le m le 10000≤m≤1000,v≤500000v le 500000v≤500000
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; typedef double db; template <class T> void read(T &x) char c; bool op = 0; while(c = getchar(), c < ‘0‘ || c > ‘9‘) if(c == ‘-‘) op = 1; x = c - ‘0‘; while(c = getchar(), c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘; if(op) x = -x; template <class T> void write(T x) if(x < 0) putchar(‘-‘), x = -x; if(x >= 10) write(x / 10); putchar(‘0‘ + x % 10); const int maxn = 15; const int maxm = 1010; const int maxt = 1 << maxn; int n,m,a,b,c,ans=INF; int frog[maxt][maxn],gorf[maxt],dis[maxn][maxn]; int main() read(n); read(m); memset(dis,0x3f,sizeof(dis)); duke(i,1,m) int x,y,z; read(x);read(y);read(z); x--;y--; dis[x][y] = dis[y][x] = min(dis[x][y],z); memset(frog,0x3f,sizeof(frog)); duke(i,1,(1 << n) - 1) duke(j,0,n - 1) if(((1 << j) | i ) == i) dis[j][j] = 0; duke(k,0,n - 1) if(dis[j][k] != INF) gorf[i] |= (1 << k); duke(i,0,n - 1) frog[1 << i][0] = 0; duke(i,2,(1 << n) - 1) for(int s0 = i - 1; s0; s0 = (s0 - 1) & i) if((gorf[s0] | i) == gorf[s0]) int sum = 0; int ss = s0 ^ i; duke(k,0,n - 1) if((1 << k) & ss) int temp = INF; duke(h,0,n - 1) if((1 << h) & s0) temp = min(temp,dis[h][k]); sum += temp; duke(j,1,n - 1) if(frog[s0][j - 1] != INF) frog[i][j] = min(frog[i][j],frog[s0][j - 1] + sum * j); int ans = INF; duke(i,0,n - 1) ans = min(ans,frog[(1 << n) - 1][i]); printf("%d ",ans); return 0;
noip2017宝藏(状压dp+贪心)(代码片段)
...明得到了一份藏宝图,藏宝图上标出了n个深埋在地下的宝藏屋,也给出了这n个宝藏屋之间可供开发的m条道路和它们的长度。小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打... 查看详情
[luogu3959noip2017]宝藏(状压dp)(代码片段)
DescriptionInput第一行两个用空格分离的正整数n,m,代表宝藏屋的个数和道路数。接下来m行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为1?n),和这条道路的长度v。Output一个正整数,表示最... 查看详情
p3959宝藏
...明得到了一份藏宝图,藏宝图上标出了nn个深埋在地下的宝藏屋,也给出了这nn个宝藏屋之间可供开发的mm条道路和它们的长度。小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面... 查看详情
lojp3959宝藏状压dpnoip(代码片段)
https://www.luogu.org/problemnew/show/P3959考场上我怎么想不出来这么写的,状压白学了。直接按层次存因为如果某个点在前面存过了则肯定结果更优所以不用在意各点的层次只用在意最深的点的层次。调的时候因为e最开始初始化太大了... 查看详情
noip2017-宝藏(代码片段)
LibreOJ链接Description给出一个\(n(n\leq12)\)个点\(m(m\leq1000)\)条边的带权无向图,求该图的一棵生成树,使得其边权×该边距根的深度之和最小。Solution既然\(n\leq12\),可以猜测是状压DP。定义\(f[dpt][s][s_1]\)表示一棵深度为\(dpt\),点集为... 查看详情
状压dp(代码片段)
这几天都在学习状压DP,总结一下,首先是状压DP的工具。类型符号规则例子按位与&同1为1,其余为09 00001001&5 000001011 &nb 查看详情
luogup3959宝藏(代码片段)
这道题正解是状压DP,不过我不会所以写一下随机化算法来骗骗分。听说当时考场上就有很多写prim然后挂掉的神仙,其实这道题是可以prim过的prim是一种基于贪心的算法,在本题中由于盲目的选择当前最优解可能会使得后面的决... 查看详情
simplestringproblem(状压dp)(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
动态规划---状压dp2(代码片段)
今天模拟,状压dp又没写出来。。。还是不会啊,所以今天搞一下这个状压dp。这里有一道状压dp的板子题:CornFields就是一道很简单的状压裸题,但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结:上题干... 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍:状态表示: 转移方程:i是当前节点,j是下一步要走的节点 子集枚举:核心代码:1。由当前枚举未知首先枚举状态,枚举S中包含的节点:枚... 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*(另类的暴力)* 一般状态数不多的时候就会开数组,但是有的状态并不好表示,于是,状压DP就产生了。 状压DP应该是分两类的,一类是压缩状态,另一类是舍弃状态。 &... 查看详情
sdnu1038.收集宝藏(dp)(代码片段)
Description有一个n*n的矩阵,矩阵每个格子中都有一些宝藏,从左上角(1,1)出发,每次只能向下或者向右移动一格,已知每个格子中宝藏的价值,求走到右下角(n,n)时能收集到的宝藏的总最大价值。Input第一行为一个整数n(1<=n<=10... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压,问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
状压dp(代码片段)
P2915[USACO08NOV]MixedUpCowsGdfs去做#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#definelllonglongusingnamespacestd;intb[25],n,m,a[25];llcnt;voiddfs(intt,int 查看详情
poj3254(状压dp)(代码片段)
CornFieldsTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:19518 Accepted:10243DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedofMbyN(1≤M≤12;1≤N≤12)squareparcels.Hewant 查看详情
b.littleponyandharmonychest(状压dp)(代码片段)
B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi≥59时,bi=1b_i=1bi=1更优。所以只需考虑bi≤59b_i\\le59bi≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情
poj3254(状压dp)(代码片段)
CornFieldsTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 20975 Accepted: 10998DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedof M by 查看详情
dp--状压dp(代码片段)
ProblemDescription互不侵犯在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。Analysisofideas把每一行的每一个状态用一个... 查看详情