POJ 3925 - 状态DP.位运算

网友投稿 587 2022-10-20

POJ 3925 - 状态DP.位运算

POJ 3925 - 状态DP.位运算

研读北大的发现这题的...书上介绍的是DFS枚举点..然后最小生成树来找答案...正好前不久做过一些状态 DP的问题..就用状态DP水过了...

对于一类点个数为n=15左右的问题...应该敏感的联想到状态DP...用n位2进制数可以在较好的所有点的状态...此题正是如此...用x ( 0<=x<=2^n) 表示当前的树中有哪些点...

这里用到了两个位运算..

一个是判断十进制整数x在二进制下的第k位是否为1...用 x & (1<

另一个是判断 十进制整数x在二进制下有多少位为1...x=x & (x-1) 要执行到x==0的次数即为x中1的个数..原因..因为总能去掉最末尾的1

其实写完之后...发现本质上枚举点做最小生成树和我这种状态DP是一样的...因为我在更新过程中就是Prim的过程...

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000000#define pi acos(-1)using namespace std; int n,m,p[20],arc[20][20],g,ans,dp[40000]; double minimal;int main(){ int i,x,y,k,w,z,v; while (~scanf("%d%d",&n,&m)) { if (!n && !m) break; for (i=1;i<=n;i++) scanf("%d",&p[i]); for (y=1;y<=n;y++) for (x=1;x<=n;x++) scanf("%d",&arc[y][x]); g=(1<dp[w]+arc[y][k]) dp[x]=dp[w]+arc[y][k]; } k=0; z=x; while (z) { k++; z=z & (z-1); } // 得到当前状态下有多少个点.. if (k==m && minimal>(dp[x]*1.0/v)) { minimal=dp[x]*1.0/v; ans=x; } } for (x=1;x<=n;x++) if (ans & (1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：程序
上一篇:CodeForces Round #140(226B) - Naughty Stone Piles
下一篇:SpriteJS- 跨平台 canvas 绘图框架
相关文章

 发表评论

暂时没有评论，来抢沙发吧~