[Leaf] [P6772] 美食家

p6772-[noi2020]-美食家---洛谷">P6772 [NOI2020] 美食家 - 洛谷

1. 题面梗概

中译中：给一张 nn 个点 mm 条边的有向图，边有权 wi∈[1,5]w_i \in [1, 5] 代表天数。每个点有权 cic_i 代表每天到达后的收益。在特定的时间 tit_i 到达特定的点 xix_i 有额外收益 yiy_i。

求从点 11 出发，恰好在第 TT 天回到点 11 的最大总收益。

n≤50,T≤109,wi∈[1,5],k≤200n \le 50, T \le 10^9, w_i \in [1, 5], k \le 200

2. 逻辑推导

最容易想到一版 DP，定义 dp[t][u]dp[t][u] 为第 tt 天到达城市 uu 的最大收益：

dp[t][v]=max⁡(u,v,w)∈E{dp[t−w][u]+cv}+fest(t,v)dp[t][v] = \max_{(u, v, w) \in E} \{ dp[t-w][u] + c_v \} + fest(t, v)

但这只能得到 40pts40 pts，原因在于 T=109T = 10^9 时，时间轴太长，无法逐日递推。我们需要优化。

2.1 矩阵快速幂

因为 TT 很大而 n,m,wn, m, w 都较小，容易想到矩阵快速幂优化。

对于传统的矩阵乘法，我们是这样定义的：

C=A×B  ⟺  C[i][j]=∑k=1nA[i][k]×B[k][j]C = A \times B \iff C[i][j] = \sum_{k=1}^{n} A[i][k] \times B[k][j]

但在本题中，DP 的转移不是相加而是取 max，我们尝试魔改一下矩阵乘法：

C=A⊕B  ⟺  C[i][j]=max⁡k=1n(A[i][k]+B[k][j])C = A \oplus B \iff C[i][j] = \max_{k=1}^{n} (A[i][k] + B[k][j])

也就是 (max,+)( max, + ) 的矩阵，可以证明这个矩阵是符合结合律的，证明略。

2.2 拆点

矩阵快速幂要求：dp[t]→dp[t+1]dp[t] \to dp[t+1] 的转移是恒定的，但本题边权 w∈[1,5]w \in [1,5]。

我们把原本的城市 uu 拆成 55 个状态节点 (u,0),(u,1),(u,2),(u,3),(u,4)(u,0), (u, 1), (u, 2), (u, 3), (u, 4)。

状态含义：(u,i)(u, i) 表示 “还有 ii 天到达城市 uu”。

内部转移：(u,i)→(u,i−1)(u, i) \to (u, i-1) 权值为 00

外部转移：对于一条边 (u,v,w)(u, v, w)，则连边 (u,0)→(v,w−1)(u,0) \to (v, w-1) 权值为 c[v]c[v]。

此时时间复杂度为 O((5n)3log⁡T)O( (5n)^3 \log T)，预期 65 pts。

以上矩阵快速幂，只能处理 k=0k = 0 的情况，也就是没有美食节的情况。

2.3 kk 的处理

注意到题目保证了任意两个美食节不在同一天举办。所以可以先将美食节按举办时间从小到大排序。

然后在任意两个美食节之间，做一遍普通的DP转移。例如，第 jj 个美食节的举办日期为 tjt_{j} ，第 j−1j−1 个美食节举办日前为 tj−1t_{j-1} ，则这段的转移就是：

dp[tj]=dp[tj−1]⊕Mtj−tj−1dp[t_{j} ]=dp[t_{j-1} ] \oplus M^{t_{j} - t_{j - 1}}

转移完成后，再令dp[tj][xj]+=yjdp[t_{j} ][x_{j} ]+=y_{j} ，也就是加上了美食节的贡献。

时间复杂度 O(k⋅(5n)3⋅log⁡T)O( k \cdot (5n)^3 \cdot \log T)，预期 75 pts。

2.4 进一步优化

我们发现所做的 kk 次转移，每次都是乘以同一个转移矩阵的若干次幂。

不妨提前预处理 2k2^k 的矩阵，也就是 (M1,M2,M4,… )(M_{1}, M_{2}, M_{4},\dots)，复杂度为 O(N3log⁡T)O( N^3 \log T)。

然后，在做每个美食节的转移时，对 dt=tj−tj−1dt = t_{j} - t_{j-1} 这个数做二进制分解，记 dt=2p1+2p2+⋯+2pldt = 2^{p_{1}} + 2^{p_{2}} + \cdots + 2^{p_{l}}，也就是 (p1,p2,…,pl)(p_{1}, p_{2}, \dots, p_{l}) 这些二进制位上为 11。

那么我们只需要用 dp[tj−1]dp[t_{j-1}]，依次乘以与处理好的 M2p1,M2p2,…,M2plM^{2^{p_{1}}}, M^{2^{p_{2}}}, \dots, M^{2^{p_{l}}}，即可得到 d[tj]d[t_{j}]。

由于 dpdp 是一个 1×5n1 \times 5n 的长条（向量），所以乘法的复杂度是 O((5n)2)O( (5n)^2 )。

所有的转移复杂度为 O(k⋅(5n)2⋅log⁡T)O( k \cdot (5n)^2 \cdot \log T)。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 50 + 5;
const int maxn2 = 250 + 5;
const int maxk = 200 + 5;
const ll inf = 1e18;

ll c[maxn];
int n, m, T, k;
int sz;

struct Mat {
    ll mat[maxn2][maxn2];
    Mat( ) { memset( mat, -0x3f, sizeof (mat) ); }
} pw[31];

// ( max, + )
Mat mul( const Mat &A, const Mat &B )
{
    Mat res;
    for( int i = 1; i <= sz; ++ i )
    {
        for( int k = 1; k <= sz; ++ k )
        {
            if( A.mat[i][k] < 0 ) continue;
            for( int j = 1; j <= sz; ++ j )
            {
                if( B.mat[k][j] < 0 ) continue;
                res.mat[i][j] = max( res.mat[i][j], A.mat[i][k] + B.mat[k][j] );
            }
        }
    }
    return res;
}

void vec_mul( ll *V, const Mat &M )
{
    static ll tmp[maxn2];
    for( int i = 1; i <= sz; ++ i ) tmp[i] = -inf;

    for( int i = 1; i <= sz; ++ i )
    {
        if( V[i] < 0 ) continue;
        for( int j = 1; j <= sz; ++ j )
        {
            if( M.mat[i][j] < 0 ) continue;
            tmp[j] = max( tmp[j], V[i] + M.mat[i][j] );
        }
    }
    
    for( int i = 1; i <= sz; ++ i ) V[i] = tmp[i];
}

struct Festival {
    int t, x, y;
    bool operator < ( const Festival &oth ) const { return t < oth.t; }
} fes[205];

int main( )
{
    ios::sync_with_stdio( 0 );
    cin.tie( 0 );
    
    cin >> n >> m >> T >> k;
    sz = 5 * n;
    for( int i = 1; i <= n; ++ i ) cin >> c[i];

    Mat base;
    for( int i = 1; i <= n; ++ i )
        for( int j = 1; j <= 4; ++ j )
            base.mat[i + j * n][i + (j - 1) * n] = 0;

    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w; cin >> u >> v >> w;
        base.mat[u][v + (w - 1) * n] = c[v];
    }

    pw[0] = base;
    for( int i = 1; i <= 30; ++ i ) pw[i] = mul( pw[i - 1], pw[i - 1] );

    for( int i = 1; i <= k; ++ i ) cin >> fes[i].t >> fes[i].x >> fes[i].y;
    sort( fes + 1, fes + k + 1 );

    ll V[maxn2];
    for( int i = 1; i <= sz; ++ i ) V[i] = -inf;
    V[1] = c[1];

    int lst = 0;
    fes[k + 1] = { T, 1, 0 };

    for( int i = 1; i <= k + 1; ++ i )
    {
        int dt = fes[i].t - lst;
        for( int p = 30; p >= 0; -- p )
            if( dt >> p & 1 ) vec_mul( V, pw[p] );
        
        if( V[fes[i].x] >= 0 ) V[fes[i].x] += fes[i].y;
        lst = fes[i].t;
    }

    if( V[1] < 0 ) cout << -1 << '\n';
    else cout << V[1] << '\n';
    return 0;
}

4. 复盘

  • 复杂度分析：O((5n)3log⁡T+k⋅(5n)2log⁡T)O( (5n)^3 \log T + k \cdot (5n)^2 \log T)

  • 碎碎念：DP 转移的矩阵加速幂优化，还有拆点技巧（也可以拆边，但是在这题不占优）。

关联笔记：树图DP | [[优化DP#矩阵快速幂]]