标签:dp

NOIP2008 传纸条

NOIP2008 传纸条

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用0表示),可以用一个0-100的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

题解:如果将题目简化为一个纸条从1,1到n,m,则dp[i][j]即可简单做出,所以类比可以想到四维的dp[i][j][k][h]表示i,j和k,h的纸条(因为从n,m到1,1等于从1,1到n,m,所以两个纸条可以都从1,1出发),那么我们就可以用O(n^4)的复杂度做出。我们还可以根据i+j=k+h将数组和时间复杂度简化到O(n^3)。
另外,我们都会注意到两个纸条是不能重合的,所以我们来看这样一个神奇的事情:

对于这个有相交的两条路径来说,他一定不是最优解,因为如下这样的路径保证优于相交,那么对于dp[i][j][i][j]来说,我们就不用管它了,只要保证他不会将该点好心值加了两遍或者遇到他取完max直接跳过都可以哦

所以在转移方程为:
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j][k-1],dp[i][j-1][k],dp[i][j-1][k-1])+w[i][j]+w[k][h];
并且if (i==k && j==h) dp[i][j][k]-=w[i][j]即可

AC代码:

0
震惊!状压dp竟是这样完成的!

震惊!状压dp竟是这样完成的!

这几天在内网挑题刷(看哪道顺眼刷哪道),然后意外之中选中了这个稀有矿井,然后baidu告诉我这是一道状压dp,然后……小迪告诉我她AC了……

那我们就来看一下这道题吧!

XYZ公司已在沿太平洋东海岸位于不同地区的几个岛屿发现了5种稀有的矿藏。该公司认为,这将是一个获利最好的机会。然而,由于金融危机,该公司并没有足够的人手和金钱在所有岛屿上建立矿田。因此,公司委员会选择了一些有较高的矿石储量岛屿,并派出一名调查员对这些岛屿制作了岛上的矿石分布调查。调查结果显示,每个岛上有许多连接在一起的村庄。由于耗费时间,调查员并没有记录的地图中的所有路径。只是记下了一条到达每个村庄的路径,从一个村庄到达另一个,有一个且只有一条路径(地图绘制像一棵树)。
该公司计划在每个岛屿的其中一个村庄建立分工厂。所有在岛上不同地方挖来的5种稀有矿产将被发送到这个分工厂,后成为一个复合金属。因此途径的道路必须被重修过,才能通过数量庞大的车队。为了尽量减少对道路交通的建设成本,公司决定扩大原有的路径,而不是兴建新的道路。此外,该公司决定兴建村庄的矿田,以确保他们的工人可以进入采矿。 (如果子工厂坐落在一个村庄中,矿田也可以建在该村庄。
输入:
第一行,包含一个整数T,表示岛屿的数目。(1<=Num<=50)
每组测试数据,第一行一个整数N(5<=N<=1000)。表示岛上村庄的个数。
接下来一行,N个数,m1, m2, … mn(0<=mi<=5),表示第i个村庄所拥有的稀有矿藏的种类,0表示该村庄没有稀有矿藏(每一个村庄至多只有一种矿藏)。
接下来N-1行,描述了这个岛上连接N个村庄的地图。
每行三个数,x,y,d(1<=x, y<=n, 1<=d<=10000), 表示从x和y两个村庄之间有一条距离为d的路。

输出:
每行输出一个整数。在每个岛上所需的最少扩建道路的长度。

有有思路的吗?有没有思路的吗?有一眼秒的吗?
所以既然都说这是一道“状压dp”了,等等……状压dp是啥?
其实就是在dp状态转移的状态用2进制的数表示出来,比如选和不选,挖和不挖。
所以,显然,我们需要首先普及一下位运算:

类型

符号

规则

例子

按位与

&

同1为1,其余为0 9 00001001

&

5 00000101

1 00000001

按位或

|

同0则0,其余为1 9 00001001

|

5 00000101

13 00001101

按位异或

^

不同则1,相同则0 9 00001001

^

5 00000101

12 00001100

取反~

~

0变1,1变0 9 00001001

~

246 11110110

左移

<<

丢掉最右,整体右移 9 00001001

>>

2

00000010

右移

>>

丢掉最左,整体左移 9 00001001

<<

2

00100100

所以我们就来考虑一下这道题吧,<它是一棵树,所以也叫树形dp,当然树形dp还是有一点思想的>,对于每一个节点,状态转移方程就是:
dp[i][a|b]=min(dp[i][a|b],dp[i][a]+dp[j][b]+dis[i][j]);
其中i是j的父亲节点,a和b为[0,31)枚举出来的在该节点的状态
为啥是31?
我们有5种矿石,即00001可以代表有第一种矿石,00100即有第三种,所以11111就是全挖到了w!

事情是不是十分明了呢?

AC代码:

蛤蛤蛤?

0