本文共 1546 字，大约阅读时间需要 5 分钟。

题意：给你n个岛屿，m条路，每个岛屿都有一个值vi，经过这个岛屿会得到这个值，规则：

1、经过所有的岛屿 sum += vi；

2、连续两个岛屿（即连通） sum += vi * vj；

3、连续三个岛屿（即两两连通）sum += vi + vj + vk；

求得到最大的值，并且问的到最大的值有多少种路线；（最后的路线/2,无向图）

dp[i][j][k] 表示第i个状态 j-->k 得到的最大值

s[i][j][k] 表示第i个状态 j-->k 得到的最大值的路线的数量

注：1001 ---> 1101       1的位置与0的位置和3的位置有关 

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef __int64 LL;#define M 1<<14LL dp[M][14][14];LL s[M][14][14];LL v[14];int map[14][14];int n,m;void DP(){    int cnt = 1 << n;    for(int i = 0;i < cnt;i++)    {        for(int j = 0;j < n;j++)        {            for(int k = 0;k < n;k++)            {                if(dp[i][j][k] == -1) continue;                for(int r = 0;r < n;r++)                {                    if(r == j || r == k || i&(1<
        
         < n;i++) { for(int j = 0;j < n;j++) { if(dp[cnt-1][i][j] == -1) continue; if(dp[cnt-1][i][j] > ans) { ans = dp[cnt-1][i][j]; num = s[cnt-1][i][j]; } else if(dp[cnt-1][i][j] == ans) num += s[cnt-1][i][j]; } } if(num) cout << ans << " " << num/2 << endl; else cout << "0 0" << endl;}int main(){ int t,u,w; cin >> t; while(t--) { cin >> n >> m; for(int i = 0;i < n;i++) cin >> v[i]; memset(map,0,sizeof(map)); memset(dp,-1,sizeof(dp)); memset(s,0,sizeof(s)); for(int i = 0;i < m;i++) { cin >> u >> w; u -- ; w --; map[u][w] = map[w][u] = 1; int st = (1 << u) + (1 << w); dp[st][u][w] = dp[st][w][u] = v[u] + v[w] + v[u] * v[w] ; s[st][u][w] = s[st][w][u] = 1; } if(n == 1){ cout << v[0] << " 1" << endl; continue; } DP(); }}
        
       
      
     
    
   

转载地址：http://ldsgi.baihongyu.com/