loj3339 美食家
Description
一张 (n) 个点 (m) 条边的有向图，每条边有权值 (w_i) 表示走完该边需要的时间，每次走到点 (i) 都可以获得 (c_i) 的收益。
在 (0s) 时，你从起点 (1) 出发，不断沿图中的边走知道 (Ts) 时回到 (1) 号点，中途不能在任何点上停留 。同时还有 (k) 个特殊收益，第 (i) 个表示如果你在 (t_i) 天时恰好在城市 (x_i) ，则会额外获得 (v_i) 的收益。请求出最大的总收益。
(nle 50,mle 501,Tle 10^9,kle 200,1le w_ile 5,1le c_ile 52501)。
Solution
首先容易想到朴素 (DP)，设 (dp_{t,x}) 表示 (ts) 时恰好到达点 (x) 的所有方案中的最大总收益，然后暴力枚举下一步走的边进行转移：
其中 (w_{t,v}) 为 (t) 时刻 (v) 点的特殊收益。
这样做的复杂度时 (mathcal O(mT)) 的。
(T) 的数据范围提示我们使用矩阵快速幂，注意到题目中保证 (w_ile 5)，因此 (dp_{t,x}) 只可能有 (ge t-5) 时间的 (dp) 值转移到时间 (t) 的所有 (dp) 值，因此会影响时间 (t) 的 (dp) 值的点只有 (5n) 个，于是可以直接将这 (5n) 个点的转移写成矩阵。
具体地，设当前需要求 (t) 时刻的所有 (dp) 值，影响它们的所有 (5n) 个 (dp) 值可以写成一个列向量：
那么新的列向量需要继承 (t-4sim t-1) 的 (dp) 值转移得到 (t) 的 (dp) 值。这个相信大家都会，本题中 (dp) 的转移是关于 (+) 与 (max) 的，但我们也可以跟普通矩阵快速幂一样做，只需要将一般矩阵乘法 ((+, imes))，变为 ((max,+))
大力写出转移矩阵，由于在 (k) 个有特殊收益的时间内需要特殊处理，因此可以将时间 (T) 分为 (k) 段依次处理，对于每一段分别进行矩阵快速幂后用列向量左乘，然后再单独处理特殊点的转移，这样做的复杂度就是 (mathcal O((5n)^3klog T)) 了。
考虑优化，每次暴力进行矩阵快速幂实际上没有必要，因为每次都对同一个矩阵取幂，那么可以预处理该矩阵的 (2^k) 次幂，复杂度为 (mathcal O((5n)^3log T))，对于每一段时间，设需要乘上一个矩阵的 (c) 次方，那么将 (c) 拆为多个 (2^k) 相加，用答案的列向量分别去乘这些矩阵，单次乘法的复杂度是 (mathcal O((5n)^2))，因此总复杂度为 (mathcal O((5n)^3log T+(5n)^2klog T))，可以通过此题。
本题的优化方法算是矩阵快速幂的一种常见套路了，建议记录一下。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=251;
const ll inf=-1e15;
int d;
struct matrix{
ll c[N][N];
inline void init(ll x){
for(int i=0;i<d;++i)
for(int j=0;j<d;++j) c[i][j]=i==j?x:inf;
}
}pw[30];
matrix operator *(const matrix &A,matrix &B){
matrix ret;
for(int i=0;i<d;++i)
for(int j=0;j<d;++j){
ret.c[i][j]=inf;
for(int k=0;k<d;++k) ret.c[i][j]=max(ret.c[i][j],A.c[i][k]+B.c[k][j]);
}
return ret;
}
int n,m,T,k,c[N];
inline int id(int x,int y){return y*n+x-1;}
struct query{
int t,x,y;
}q[N];
bool operator <(const query &a,const query &b){return a.t<b.t;}
typedef vector<ll> vec;//列向量
vec operator *(const vec &A,const matrix &B){
vec ret;ret.resize(d);
for(int i=0;i<d;++i){
ret[i]=inf;
for(int j=0;j<d;++j)
ret[i]=max(ret[i],A[j]+B.c[i][j]);
}
return ret;
}
int main(){
// freopen("delicacy.in","r",stdin);
// freopen("delicacy.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&T,&k);d=n*5;
pw[0].init(inf);
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
for(int j=0;j<4;++j) pw[0].c[id(i,j)][id(i,j+1)]=0;
}
for(int i=1,u,v,w;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
pw[0].c[id(v,4)][id(u,5-w)]=c[v];
}
for(int i=1;(1<<i)<=T;++i) pw[i]=pw[i-1]*pw[i-1];
for(int i=1;i<=k;++i) scanf("%d%d%d",&q[i].t,&q[i].x,&q[i].y);
q[++k]=(query){T,1,0};
sort(q+1,q+k+1);
vec ret;ret.resize(d);
for(int i=0;i<d;++i) ret[i]=inf;
ret[id(1,4)]=c[1];
for(int l=1,r=0;l<=k;l=r+1){
r=l;
while(r<k&&q[r+1].t==q[l].t) ++r;
int tmp=q[l].t-q[l-1].t;
// cout<<l<<" "<<r<<" "<<tmp<<endl;
if(tmp>0){
for(int i=0;(1<<i)<=tmp;++i)
if(tmp&(1<<i)) ret=ret*pw[i];
}
for(int i=l;i<=r;++i)
ret[id(q[i].x,4)]+=q[i].y;
}
printf("%lld
",ret[id(1,4)]<=-1?-1:ret[id(1,4)]);
return 0;
}