CTSC2011 幸福路径

一道不错的动态规划题目，需要一定思维。

Link

首先，考虑最终路径的形态：如果该路径是有限长度的，那么一定是一条简单路径；如果该路径是无限长度的，那一定是一段简单路径与一个环拼接而成。

证明：如果我们当前经过了至少一个环，那么经过这个环即是最优答案，向外扩展一定不比重复该环优。

那么我们可以记 \(f_{i,j,k}\) 表示从 \(i\) 到 \(j\)，经过了 \(k\) 条边（不包括节点 \(i\)）的最大收益。

计算第一种形态，此时 \(k\leq n\)，也就是对于所有 \(1\leq k\leq n\)，\(f_{i,j,k}=\max\limits_{j'\rightarrow j}\{f_{i,j',k-1}+w_{j'}\times\rho^k\}\)。

考虑第二种形态，我们记录 \(c_i\) 表示从 \(i\) 开始重复走环的最大收益，可以利用等比数列求和公式得出，\(c_i=\max\limits_{k=1}^{n}\left\{\dfrac{f_{i,i,k}}{1-\rho^k}\right\}\)。

之后我们可以枚举简单路径的终点，然后拼接上重复走环的收益，计算答案即可。

for(int k = 1; k <= n; k++)
    for(int j = 1; j <= n; j++)
        for(auto t : e[j])
            for(int i = 1; i <= n; i++)
                if(f[i][j][k - 1] >= -eps)
                    f[i][t][k] = max(f[i][t][k], f[i][j][k - 1] + pmi[k] * w[t]);
for(int i = 1; i <= n; i++)
    for(int k = 1; k <= n; k++)
        if(f[i][i][k] >= -eps) c[i] = max(c[i], f[i][i][k] / (1.00 - pmi[k]));
for(int i = 1; i <= n; i++)
    for(int k = 0; k <= n; k++)
        ans = max(ans, w[v0] + f[v0][i][k] + c[i] * pmi[k]);