poj 2288(状压DP)

发表于 | 分类于 | | + s

poj 2288
题意：求一个无向图中的一条哈密顿路，这条路价值最大。
价值计数方法为：所有点权+两连续点权积+三连续点构成三角形积 (算法竞赛进阶指南例题)

这种方程的转移能力还是差。。
设$dp(S,i,j)$为状态为$S$，最后访问的两个点依次为$i,j$的最大值
那么转移就是$dp(S,i,j)=dp(S-k,j,k)+val_i+val_i \cdot val_j$，如果$i,k$连通则加上$val_i \cdot val_j \cdot val_k$
这个转移相当于当前路径是$k->j->i$，从$(k,j)$转移到$(j,i)$

初始化$dp(S, i, j) = val_i + val_j + val_i \cdot val_j$，两点连通对答案的贡献
然后之后的 DP 都从这些转移过来，记得判无效状态！

知识点：
1、DP检查方法：1、转移是否漏 2、转移是否从无效状态转移

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, m, val[15], G[15][15], dp[(1 << 13) + 5][15][15], cnt[(1 << 13) + 5][15][15];

    void clean() {
        ms(G, 0), ms(dp, 0), ms(cnt, 0);
    }
    int solve() {
        scanf("%lld%lld", &n, &m);
        clean();
        for (LL i = 1; i <= n; ++i) scanf("%lld", &val[i]);
        if (n == 1) return printf("%lld %lld\n", val[1], 1ll), 0;
        for (LL a, b, i = 1; i <= m; ++i) {
            scanf("%lld%lld", &a, &b);
            G[a][b] = G[b][a] = 1;
        }
        for (LL u = 1; u <= n; ++u) {
            for (LL v = 1; v <= n; ++v) if (u != v && G[u][v]) {
                dp[(1 << (u - 1)) + (1 << (v - 1))][u][v] = val[u] * val[v] + val[u] + val[v];
                cnt[(1 << (u - 1)) + (1 << (v - 1))][u][v] = 1;
                //cerr << "???" << dp[(1 << (u - 1)) + (1 << (v - 1))][u][v] << " u" << u << " v" << v << endl;
            }
        }
        for (LL S = 0; S < (1 << n); ++S) {
            for (LL i = 1; i <= n; ++i) if (S & (1 << (i - 1))) {
                for (LL j = 1; j <= n; ++j) if (i != j && S & (1 << (j - 1)) && G[i][j]) {
                    for (LL k = 1; k <= n; ++k) if (k != i && k != j && S & (1 << (k - 1)) && G[k][j] && dp[S ^ (1 << (i - 1))][j][k] > 0) {
                        LL whw = dp[S ^ (1 << (i - 1))][j][k] + val[i] + val[i] * val[j] + G[k][i] * val[i] * val[j] * val[k];
                        if (dp[S][i][j] < whw) {
                            dp[S][i][j] = whw;
                            cnt[S][i][j] = cnt[S ^ (1 << (i - 1))][j][k];
                        } else if (dp[S][i][j] == whw) cnt[S][i][j] += cnt[S ^ (1 << (i - 1))][j][k];
                    }
                }
            }
        }
        LL ans1 = 0ll, ans2 = 0ll;
        for (LL i = 1; i <= n; ++i) 
        for (LL j = 1; j <= n; ++j) {
            if (dp[(1 << n) - 1][i][j] > ans1) ans1 = dp[(1 << n) - 1][i][j], ans2 = cnt[(1 << n) - 1][i][j];
            else if (dp[(1 << n) - 1][i][j] == ans1) ans2 += cnt[(1 << n) - 1][i][j];
        }
        printf("%lld %lld\n", ans1, ans2 / 2ll);
        return 0; 
    }
}
int main() {
    int q; scanf("%d", &q);
    while (q--) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------