Prob.1[动态规划]POJ 2288 islands and bridges 二进制状压DP+预处理 Upd:2020.2.29

http://poj.org/problem?id=2288

1.常见的二进制表示:

将n位二进制数取出第k位:(n>>k)&1

将n为二进制数取出第0~k-1位:n&((1<<k)-1)

将n的第k位取反:n Xor (1<<k)

将n的第k位赋成1:n | (1<<k)

将n的第k位改成0:n&(~(1<<k))

2.题目分析:

https://blog.csdn.net/j\_sure/article/details/43459211

3.残缺代码:计数错误。

/*
1.题目中让我们找到最优的汉密尔顿路径,要求权值最大,同时要求最优路径有几条?
2.我们考虑如何实现计算权值?权值可以分为三部分:
(1)由路径上的所有的点权值和
(2)考虑路径上相邻两点权值的乘积和
(3)考虑路径上的回路三角形的连乘积的贡献值
3.分析题目:

因为最多只有13个点,我们考虑用一个13位的二进制数表示每个点是否被经过了。如果为1则为经过,如果为0则为未经过。然后因为计算中涉及到连续的三个三角形,我们在设计状态的时候应该设成

dp[s][i][j],其中s用来维护当前的状态,表示当前位置为i,前一个点为j时的最大哈密尔顿值。num[s][i][j]用于维护这样的路径条数。

在经过的点不超过三个之前,存在这样的初始化:对于任意的边(i,j),我们可以得到:dp[1<<i | 1<<j ][i][j]=val[i]+val[j]+val[i]*val[j] 因为不存在三角形的情况

然后,当n>=3 时,如果状态s满足:i,j均在s中且i,j之间有通路,找到一个与j相连的点k并且k不在s内,扩展k的状态:

dp[s|(1<<k)][j][k]=max{dp[s|(1<<k)][j][k],dp[s][i][j]+val[k]+val[k]*val[j]+val[k]*val[j]*val[i]*book[i][k]};

book[i][j]表示(i,j)两点之间的连通性,如果为真则表示联通。当判断三角形的时候,因为(i,j),(j,k)之间一定是联通的,我们只需要判断是否在(i,k)之间有通路即可!如果通就加上,反之没有贡献,乘上book[i]k]即可

*/
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=(1<<14);
int q,n,m;
ll v[15];
ll dp[N][14][14],cnt[N][14][14],Cnt,Ans;
bool book[14][14];
void Pre_work()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(book[i][j])
{
dp[(1<<i-1)|(1<<j-1)][i][j]=v[i]+v[j]+v[i]*v[j];
cnt[(1<<i-1)|(1<<j-1)][i][j]=1;
}
}
void DP()
{
for(int i=1;i<=(1<<n)-1;i++)
for(int j=1;j<=n;j++)if(i & (1<<j-1)){
for(int t=1;t<=n;t++) if(j!=t && (i & (1<<t-1)))
{
if( dp[i][j][t] && book[j][t] )
{
for(int k=1;k<=n;k++)
if( ! (i&(1<<k-1)) && book[t][k] && k!=j)
{
ll tmp=0;
tmp=dp[i][j][t]+v[k]+v[k]*v[t]+v[k]*v[t]*v[j]*book[k][j];
if(tmp>dp[i|(1<<k-1)][t][k])
{
dp[i|(1<<k-1)][t][k]=tmp;
cnt[i|(1<<k-1)][t][k]=cnt[i][j][t];
}
else if(tmp==dp[i|(1<<k-1)][t][k])
{
cnt[i|(1<<k-1)][t][k]+=cnt[i][j][t];
}
}
}
}
}
}
int main()
{
int x,y;
scanf("%d",&q);
while(q--)
{
Ans=0;
Cnt=0;
memset(book,0,sizeof(book));
memset(dp,0,sizeof(dp));
memset(cnt,0,sizeof(cnt));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&v[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
book[x][y]=1;
book[y][x]=1;
}
Pre_work();
DP();
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(book[i][j])
{
if(dp[(1<<n)-1][i][j]>Ans)
{
Ans=dp[(1<<n)-1][i][j];
Cnt=cnt[(1<<n)-1][i][j];
}
else if(dp[(1<<n)-1][i][j]==Ans)
Cnt+=cnt[(1<<n)-1][i][j];
}
Cnt/=2;
printf("%lld %lld\n",Ans,Cnt);
}
return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。