本文主要是介绍POJ 2288 Islands and Bridges(状态压缩)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：这题虽然看似很简单其实如果细心的话也不难，但是wa 了 n 次，wa 在了统计最优解个数上，开始没有开数组然后最后统计达到目标状态最优解的个数，这样是不对的，因为你只记录了最终的状态，可能在形成最优解的过程中有许多方法构成了最优解。
解题思路：
(1) 、这题很容易想到状态方程 ： dp[ S ^ (1<<k) ] [ j ] [ k ] = max(dp[ S ^ (1<<k) ] [ j ] [ k ] , dp[ S ] [ i ] [ j ] + Wk ) ; dp[ S ^ (1<<k) ] [ j ] [ k ] 代表达到状态S ^ (1<<k) 并以 j , k 结尾的路径最优解 ；
(2)、还要有记录路径的数组，因为有可能一种状态有许多方法构成 ，注意用 long long or __int64 ;
(3)、注意只有一个点的情况。
代码：
#include<iostream>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const int INF = 9999999 ;
const INT MY = 10 + 10 ;
const INT MX = (1<<13) + 10 ;
INT n ,m ;
INT dp[MX][MY][MY] ,v[MY] ,w[MY][MY] ,num[MX][MY][MY] ;
void DP()
{for(INT S = 0 ;S < (1<<n) ;S++)for(INT i = 0 ;i < n ;i++)for(INT j = 0 ;j < n ;j++)if(dp[S][i][j] != -1){for(INT k = 0 ;k < n ;k++){if(k == i || k == j || S & (1<<k) || !w[j][k]) continue ;INT mx = v[k] + v[j]*v[k] + dp[S][i][j] ;if(w[i][k]) mx += v[i]*v[j]*v[k] ;INT& best = dp[S^(1<<k)][j][k] ;if(best < mx){best = mx ;num[S^(1<<k)][j][k] = num[S][i][j] ;}else if(best == mx)num[S^(1<<k)][j][k] += num[S][i][j] ;}}INT sum = 0 ,ans = -1 ;for(INT i = 0 ;i < n ;i++)for(INT j = 0 ;j < n ;j++){if(dp[(1<<n)-1][i][j] == -1) continue ;if(dp[(1<<n)-1][i][j] > ans){ans = dp[(1<<n)-1][i][j] ;sum = num[(1<<n)-1][i][j] ;}else if(dp[(1<<n)-1][i][j] == ans)sum += num[(1<<n)-1][i][j] ;}if(sum)cout<<ans<<" "<<sum/2<<endl ;else cout<<"0 0"<<endl ;
}
int main()
{INT Tx ;scanf("%I64d",&Tx) ;while(Tx--){scanf("%I64d%I64d",&n,&m) ;for(INT i = 0 ;i < n ;i++)scanf("%I64d",&v[i]) ;memset(w ,0 ,sizeof(w)) ;memset(dp ,-1 ,sizeof(dp)) ;memset(num ,0 ,sizeof(num)) ;for(INT i = 0 ;i < m ;i++){INT x ,y ;scanf("%I64d%I64d",&x ,&y) ;x-- ; y-- ;w[x][y] = w[y][x] = 1 ;INT S = (1<<x) + (1<<y) ;//初始化两个点dp[S][x][y] = dp[S][y][x] = v[x] + v[y] + v[x]*v[y] ;num[S][x][y] = 1 ;num[S][y][x] = 1 ;}if(n == 1) //特殊处理{cout<<v[0]<<" "<<1<<endl ;continue ;}DP() ;}return 0 ;
}
这篇关于POJ 2288 Islands and Bridges(状态压缩)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
