自动搬运

查看原文

来自洛谷，原作者为

	duyi 大家好我是于之航爸爸

搬运于2025-08-24 22:23:49，当前版本为作者最后更新于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$都较小，容易想到用矩阵快速幂优化。

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

$$C=A\times B \Leftrightarrow C[i][j] = \sum_{k=1}^{n}A[i][k]\times B[k][j] $$

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

$$C=A\otimes B \Leftrightarrow C[i][j] = \max_{k=1}^{n}\{A[i][k]+B[k][j]\} $$

也就是把原来外层的$+$换成$\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;
}