「NOI2020」 美食家 【矩阵快速幂】
2021/7/1 23:53:47
本文主要是介绍「NOI2020」 美食家 【矩阵快速幂】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
loj3339 美食家
Description
一张 \(n\) 个点 \(m\) 条边的有向图,每条边有权值 \(w_i\) 表示走完该边需要的时间,每次走到点 \(i\) 都可以获得 \(c_i\) 的收益。
在 \(0s\) 时,你从起点 \(1\) 出发,不断沿图中的边走知道 \(Ts\) 时回到 \(1\) 号点,中途不能在任何点上停留 。同时还有 \(k\) 个特殊收益,第 \(i\) 个表示如果你在 \(t_i\) 天时恰好在城市 \(x_i\) ,则会额外获得 \(v_i\) 的收益。请求出最大的总收益。
\(n\le 50,m\le 501,T\le 10^9,k\le 200,1\le w_i\le 5,1\le c_i\le 52501\)。
Solution
首先容易想到朴素 \(DP\),设 \(dp_{t,x}\) 表示 \(ts\) 时恰好到达点 \(x\) 的所有方案中的最大总收益,然后暴力枚举下一步走的边进行转移:
\[dp_{t,v}=\max(dp_{t,v},dp_{t-1,u}+c_v+w_{t,v}) \]其中 \(w_{t,v}\) 为 \(t\) 时刻 \(v\) 点的特殊收益。
这样做的复杂度时 \(\mathcal O(mT)\) 的。
\(T\) 的数据范围提示我们使用矩阵快速幂,注意到题目中保证 \(w_i\le 5\),因此 \(dp_{t,x}\) 只可能有 \(\ge t-5\) 时间的 \(dp\) 值转移到时间 \(t\) 的所有 \(dp\) 值,因此会影响时间 \(t\) 的 \(dp\) 值的点只有 \(5n\) 个,于是可以直接将这 \(5n\) 个点的转移写成矩阵。
具体地,设当前需要求 \(t\) 时刻的所有 \(dp\) 值,影响它们的所有 \(5n\) 个 \(dp\) 值可以写成一个列向量:
\[\begin{pmatrix} dp_{1,t-5}\\ dp_{2,t-5}\\ \dots\\ dp_{n,t-5}\\ dp_{1,t-4}\\ \dots\\ dp_{n,t-4}\\ \dots\\ dp_{1,t-1}\\ \dots\\ dp_{n,t-1} \end{pmatrix} \]那么新的列向量需要继承 \(t-4\sim t-1\) 的 \(dp\) 值转移得到 \(t\) 的 \(dp\) 值。这个相信大家都会,本题中 \(dp\) 的转移是关于 \(+\) 与 \(\max\) 的,但我们也可以跟普通矩阵快速幂一样做,只需要将一般矩阵乘法 \((+,\times)\),变为 \((\max,+)\)
大力写出转移矩阵,由于在 \(k\) 个有特殊收益的时间内需要特殊处理,因此可以将时间 \(T\) 分为 \(k\) 段依次处理,对于每一段分别进行矩阵快速幂后用列向量左乘,然后再单独处理特殊点的转移,这样做的复杂度就是 \(\mathcal O((5n)^3k\log T)\) 了。
考虑优化,每次暴力进行矩阵快速幂实际上没有必要,因为每次都对同一个矩阵取幂,那么可以预处理该矩阵的 \(2^k\) 次幂,复杂度为 \(\mathcal O((5n)^3\log T)\),对于每一段时间,设需要乘上一个矩阵的 \(c\) 次方,那么将 \(c\) 拆为多个 \(2^k\) 相加,用答案的列向量分别去乘这些矩阵,单次乘法的复杂度是 \(\mathcal O((5n)^2)\),因此总复杂度为 \(\mathcal O((5n)^3\log T+(5n)^2k\log 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\n",ret[id(1,4)]<=-1?-1:ret[id(1,4)]); return 0; }
这篇关于「NOI2020」 美食家 【矩阵快速幂】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)