博主有幸参加了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)，把原来内层的( imes)换成(+)。可以证明，这个矩阵乘法仍然是成立的，并且满足原来的种种性质（比如结合律，其实矩阵快速幂优化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)^3log T))。
注意到(m)可能比(n)大不少，所以可以把拆边改成拆点。具体来说，把一个点(u)，变成(u_1 o u_2 o dots o 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)^3log 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] exttt{+=}y_j)。也就是加上了美食节的贡献。
最后，如果(t_k eq T)，再从(dp[t_k])转移到(dp[T])就行。
直接按此做法实现的话，时间复杂度(O(kcdot (5n)^3cdot log T))。可以通过(kleq 10)的部分分，结合前面的暴力，期望得分(75)分。
进一步优化
我们发现所做的(k)次转移，每次都是乘以同一个转移矩阵的若干次幂。
我们考虑把【(G)的【(2)的次幂】次幂】（也就是(G^1,G^2,G^4,G^8,G^{16},dots ,G^{2^{29}})）预处理出来。预处理的时间复杂度为(O((5n)^3log T))。
然后，在做每个美食节的转移时，对((t_j-t_{j-1}))这个数做二进制分解，设(t_j-t_{j-1}=2^{p_1}+2^{p_2}+dots +2^{p_l})，也就是(p_1dots 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 imes 5n)的“长条”（又叫向量）而不是一个真正的矩阵，所以每次乘法的时间复杂度只有(O((5n)^2))。所有转移的总复杂度(O(kcdot (5n)^2cdot log T))。
总时间复杂度(O((5n)^3log T+ kcdot (5n)^2log T))。
这个优化方法和NOI Online 3 魔法值这题很类似。
参考代码
友情提醒，在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;
}