题解 P6772 【[NOI2020]美食家】

duyi · 2020-08-21 21:35:00 · 题解

LOJ3339 「NOI2020」美食家

题目链接

博主有幸参加了NOI2020，考场上的经历和心得请见这篇文章。这里就不唠叨了。

本题题解

朴素DP

考虑前两档部分分，也就是T没那么大的时候。我们可以做一个简单的DP。设dp[i][u]表示在第i天，走到了图上的节点u，一路上总共能获得的最大愉悦值。转移时，可以枚举点u的一条出边(u,v,w)，然后用dp[i][u]+c[v]去更新dp[i+w][v]，当然，如果第i+w天点v恰好在举办美食节，还要加上额外产生的愉悦值。

因为保证了w>0，所以这个DP满足无后效性，状态非常合理。时间复杂度O(T(n+m))，期望得分40分。加上环的部分分（简单特判），可以得到50分。

矩阵优化

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

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

但在本题中，DP的转移不是相加而是取\max。我们根据本题中的需要，定义一种新的矩阵乘法，不妨记为\otimes：

也就是把原来外层的+换成\max，把原来内层的\times换成+。可以证明，这个矩阵乘法仍然是成立的，并且满足原来的种种性质（比如结合律，其实矩阵快速幂优化DP的本质就是用到结合律）。证明略。

值得一提的是，这种重新定义的矩阵乘法，在一类动态DP问题中经常用到。例如NOIP2018 保卫王国。

回到我们的DP。先只考虑k=0，也就是没有美食节的情况。

发现从dp[i][\dots]转移到dp[i+w][\dots]不太好处理（一般的矩阵快速幂优化DP，只会从i转移到i+1）。但是我们发现w很小，\leq 5，所以可以考虑把原来的一条边，拆成w条边。也就是原本的(u,v,w)，拆成：(u,e_1,w),(e_1,e_2,0),\dots,(e_{w-2},e_{w-1},0),(e_{w-1},v,0)。这样虽然点数变多了（变成了n+4m），但是只会从i转移到i+1了，可以用矩阵快速幂优化DP。

具体来说，我们根据两个点之间相连的边权（没有边就是-\inf，有边边权就是0或w，前面已经标出），构造一个转移矩阵G。则dp[i]=dp[i-1]\otimes G。答案就是dp[T][1] = (dp[1]\otimes G^T)[1]。

时间复杂度O((n+4m)^3\log T)。

注意到m可能比n大不少，所以可以把拆边改成拆点。具体来说，把一个点u，变成u_1\to u_2\to \dots \to u_5的这样一个结构，边权都是0。出发点设为1_1。对于一条边(u,v,w)，我们从u_w向v_1连一条边权为c[v]的边。这样相当于要先从u_1走到u_w，再从u_w走到v，刚好经过了w条边，也就是起到了从dp[i]转移到dp[i+w]的效果。

时间复杂度优化为O((5n)^3\log T)。可以通过k=0的部分分。结合前面的暴力，期望得分65分。

k个美食节怎么处理？

以上的矩阵快速幂，目前还只能处理k=0，也就是没有美食节的情况。考虑k>0时怎么做。

注意到题目保证了任意两个美食节不在同一天举办。所以可以先将美食节按举办时间从小到大排序。然后在任意两个美食节之间，做一遍普通的DP转移。例如，第j个美食节的举办日期为t_j，第j-1个美食节举办日前为t_{j-1}，则这段的转移就是：dp[t_{j}] = dp[t_{j-1}]\otimes G^{t_{j}-t_{j-1}}。转移完成后，再令dp[t_j][x_j]\texttt{+=}y_j。也就是加上了美食节的贡献。

最后，如果t_k\neq T，再从dp[t_k]转移到dp[T]就行。

直接按此做法实现的话，时间复杂度O(k\cdot (5n)^3\cdot \log T)。可以通过k\leq 10的部分分，结合前面的暴力，期望得分75分。

进一步优化

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

我们考虑把【G的【2的次幂】次幂】（也就是G^1,G^2,G^4,G^8,G^{16},\dots ,G^{2^{29}}）预处理出来。预处理的时间复杂度为O((5n)^3\log T)。

然后，在做每个美食节的转移时，对(t_j-t_{j-1})这个数做二进制分解，设t_j-t_{j-1}=2^{p_1}+2^{p_2}+\dots +2^{p_l}，也就是p_1\dots p_l这些二进制位上为1。那么我们只需要用dp[t_{j-1}]，依次乘以预处理好的G^{2^{p_1}},G^{2^{p_2}},\dots,G^{2^{p_l}}，即可得到dp[t_j]。而因为dp[i]是一个1\times 5n的“长条”（又叫向量）而不是一个真正的矩阵，所以每次乘法的时间复杂度只有O((5n)^2)。所有转移的总复杂度O(k\cdot (5n)^2\cdot \log T)。

总时间复杂度O((5n)^3\log T+ k\cdot (5n)^2\log T)。

这个优化方法和NOI Online 3 魔法值这题很类似。

参考代码

在LOJ查看

友情提醒，在LOJ提交时，记得开freopen，也就是和考场上要求一样。

//problem:LOJ3339
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}

const int MAXN = 50, MAXM = 501, MAXW = 5, MAXK = 200;
const int LOGT = 29;
const int MT_SIZE = MAXN*5;
const ll LL_INF = 1e18;

struct Matrix{
    ll a[MT_SIZE+5][MT_SIZE+5];
    int size;
    void identity() {
        for(int i=1;i<=size;++i) {
            for(int j=1;j<=size;++j){
                a[i][j] = (i==j ? 0 : -LL_INF);
            }
        }
    }
    Matrix(){
        for(int i=1;i<=MT_SIZE;++i)
            for(int j=1;j<=MT_SIZE;++j)
                a[i][j] = -LL_INF;
        size=0;
    }
};
Matrix operator * (const Matrix& A, const Matrix& B) {
    Matrix C;
    assert(A.size==B.size);
    C.size = A.size;
    for(int i=1;i<=A.size;++i){
        for(int j=1;j<=A.size;++j){
            for(int k=1;k<=A.size;++k){
                if(A.a[i][k] == -LL_INF || B.a[k][j] == -LL_INF)
                    continue;
                ckmax(C.a[i][j], A.a[i][k]+B.a[k][j]);
            }
        }
    }
    return C;
}
Matrix mat_pow(Matrix X,int i) {
    Matrix Y;
    Y.size = X.size;
    Y.identity();
    while(i){
        if(i&1)
            Y=Y*X;
        X=X*X;
        i>>=1;
    }
    return Y;
}

int n,m,T,K,c[MAXN+5];
int id[MAXN+5][MAXW+5],cnt_id;

struct Event{
    int t,u,w;
    bool operator < (const Event& rhs) const {
        return t < rhs.t;
    }
}ev[MAXK+5];

Matrix trans,pow_of_trans[LOGT+1];
void init_pow_of_trans() {
    pow_of_trans[0] = trans;
    for(int i=1; i<=LOGT; ++i) {
        pow_of_trans[i] = pow_of_trans[i-1] * pow_of_trans[i-1];
    }
}
void mul_pow_of_trans(Matrix& A, int mi) {
    // O(size^2 * log k)
    for(int bit=0; bit<=LOGT; ++bit) {
        if((mi>>bit) & 1) {
            //向量乘矩阵
            Matrix res;
            res.size=A.size;
            for(int j=1; j<=A.size; ++j) {
                for(int k=1; k<=A.size; ++k) {
                    if(A.a[1][k] == -LL_INF || pow_of_trans[bit].a[k][j] == -LL_INF)
                        continue;
                    ckmax(res.a[1][j], A.a[1][k] + pow_of_trans[bit].a[k][j]);
                }
            }
            A = res;
        }
    }
}

int main() {
//  freopen("delicacy.in", "r", stdin);
//  freopen("delicacy.out", "w", stdout);
    cin >> n >> m >> T >> K;
    for(int i=1;i<=n;++i) {
        cin >> c[i];
    }
    trans.size = n*5;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=5;++j) {
            id[i][j] = ++cnt_id;
        }
        for(int j=1;j<5;++j) {
            trans.a[id[i][j]][id[i][j+1]] = 0;
        }
    }
    for(int i=1;i<=m;++i) {
        int u,v,w;
        cin >> u >> v >> w;
        trans.a[id[u][w]][id[v][1]]=c[v];
    }
    for(int i=1; i<=K; ++i) {
        cin >> ev[i].t >> ev[i].u >> ev[i].w;
    }
    sort(ev+1, ev+K+1);

    Matrix A;
    A.size = n*5;
    A.a[1][id[1][1]] = c[1];
    init_pow_of_trans();

    int last_time = 0;
    for(int i=1; i<=K; ++i) {
        mul_pow_of_trans(A, ev[i].t - last_time);
        // 相当于: A = A * mat_pow(trans, ev[i].t - last_time);
        if(A.a[1][id[ev[i].u][1]] != -LL_INF) {
            A.a[1][id[ev[i].u][1]] += ev[i].w;
        }
        last_time = ev[i].t;
    }
    if(last_time != T) {
        mul_pow_of_trans(A, T - last_time);
    }
    if(A.a[1][id[1][1]] == -LL_INF)
        cout << -1 << endl;
    else
        cout << A.a[1][id[1][1]] << endl;
    return 0;
}