### [Link](https://www.luogu.com.cn/problem/P6772) 发现 $w_i\le5$ ，所以考虑拆点或拆边，因为边数比较多，所以拆点。 当 $k=0$ 时，设 $f[i][j]$ 表示到了 $i$ 时刻，到了 $j$ 号点的方案数，若 $x,j$ 相邻，则$f[i][j]=\max(f[i-1][x]+c[j])$，我们发现这个东西可以写成矩阵的形式，把矩乘中的 $+$ 改成 $\max$ ，$\times$ 改成 $+$，同时还满足结合律，我们就可以用矩阵快速幂加速递推了。 但这样太慢了，考虑最后答案是 $a\times M^T$，$a$ 是一个向量，$M$ 是一个矩阵，矩阵乘法的复杂度是 $n^3$ 的，但向量乘矩阵是 $n^2$ 的，我们可以预处理出 $M^1,M^2,M^4,M^8\cdots$，然后把 $M$ 二进制分解一下，把 $a$ 对应乘过去就好了。 当 $k$ 不等于 $0$ 时，我们可以按存在美食节分成好几段，每一段分开来做，在加上美食节的贡献就好了。 时间复杂度：$O((5n)^3\log T+k\cdot (5n)^2\log T)$ ### CODE ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=260; int n, m, T, k, c[N], tot, id[N][6]; struct matrix { int n, m; long long x[N][N]; matrix() {memset(x, -10, sizeof x);} friend matrix operator*(matrix a, matrix b) { matrix c; c.n=a.n, c.m=b.m; for (int i=1; i<=c.n; i++) for (int k=1; k<=c.m; k++) for (int j=1; j<=c.m; j++) c.x[i][j]=max(c.x[i][j], a.x[i][k]+b.x[k][j]); return c; } } tmp, a[35], f; struct node {int t, x, v;} b[N]; signed main() { n=read(), m=read(), T=read(), k=read(); for (int i=1; i<=n; i++) c[i]=read(); for (int i=1; i<=n; i++) { for (int j=1; j<=5; j++) id[i][j]=++tot; for (int j=1; j<5; j++) tmp.x[id[i][j]][id[i][j+1]]=0; } for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); tmp.x[id[x][z]][id[y][1]]=c[y]; } tmp.n=tmp.m=tot, a[0]=tmp; for (int i=1; i<=30; i++) a[i]=a[i-1]*a[i-1]; for (int i=1; i<=k; i++) b[i].t=read(), b[i].x=read(), b[i].v=read(); sort(b+1, b+k+1, [](node x, node y){return x.t<y.t;}); f.n=1, f.m=tot, f.x[1][id[1][1]]=c[1]; for (int i=1; i<=k; i++) { for (int j=0; j<=30; j++) if (((b[i].t-b[i-1].t)>>j)&1) f=f*a[j]; f.x[1][id[b[i].x][1]]+=b[i].v; } for (int j=0; j<=30; j++) if (((T-b[k].t)>>j)&1) f=f*a[j]; if (f.x[1][1]<0) puts("-1"); else printf("%lld\n", f.x[1][1]); return 0; } ``` Loading... ### [Link](https://www.luogu.com.cn/problem/P6772) 发现 $w_i\le5$ ，所以考虑拆点或拆边，因为边数比较多，所以拆点。 当 $k=0$ 时，设 $f[i][j]$ 表示到了 $i$ 时刻，到了 $j$ 号点的方案数，若 $x,j$ 相邻，则$f[i][j]=\max(f[i-1][x]+c[j])$，我们发现这个东西可以写成矩阵的形式，把矩乘中的 $+$ 改成 $\max$ ，$\times$ 改成 $+$，同时还满足结合律，我们就可以用矩阵快速幂加速递推了。 但这样太慢了，考虑最后答案是 $a\times M^T$，$a$ 是一个向量，$M$ 是一个矩阵，矩阵乘法的复杂度是 $n^3$ 的，但向量乘矩阵是 $n^2$ 的，我们可以预处理出 $M^1,M^2,M^4,M^8\cdots$，然后把 $M$ 二进制分解一下，把 $a$ 对应乘过去就好了。 当 $k$ 不等于 $0$ 时，我们可以按存在美食节分成好几段，每一段分开来做，在加上美食节的贡献就好了。 时间复杂度：$O((5n)^3\log T+k\cdot (5n)^2\log T)$ ### CODE ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=260; int n, m, T, k, c[N], tot, id[N][6]; struct matrix { int n, m; long long x[N][N]; matrix() {memset(x, -10, sizeof x);} friend matrix operator*(matrix a, matrix b) { matrix c; c.n=a.n, c.m=b.m; for (int i=1; i<=c.n; i++) for (int k=1; k<=c.m; k++) for (int j=1; j<=c.m; j++) c.x[i][j]=max(c.x[i][j], a.x[i][k]+b.x[k][j]); return c; } } tmp, a[35], f; struct node {int t, x, v;} b[N]; signed main() { n=read(), m=read(), T=read(), k=read(); for (int i=1; i<=n; i++) c[i]=read(); for (int i=1; i<=n; i++) { for (int j=1; j<=5; j++) id[i][j]=++tot; for (int j=1; j<5; j++) tmp.x[id[i][j]][id[i][j+1]]=0; } for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); tmp.x[id[x][z]][id[y][1]]=c[y]; } tmp.n=tmp.m=tot, a[0]=tmp; for (int i=1; i<=30; i++) a[i]=a[i-1]*a[i-1]; for (int i=1; i<=k; i++) b[i].t=read(), b[i].x=read(), b[i].v=read(); sort(b+1, b+k+1, [](node x, node y){return x.t<y.t;}); f.n=1, f.m=tot, f.x[1][id[1][1]]=c[1]; for (int i=1; i<=k; i++) { for (int j=0; j<=30; j++) if (((b[i].t-b[i-1].t)>>j)&1) f=f*a[j]; f.x[1][id[b[i].x][1]]+=b[i].v; } for (int j=0; j<=30; j++) if (((T-b[k].t)>>j)&1) f=f*a[j]; if (f.x[1][1]<0) puts("-1"); else printf("%lld\n", f.x[1][1]); return 0; } ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏