P6772 [NOI2020] 美食家（矩阵快速幂）

前言

无能狂怒。
见过甚至写过博客的trick，但就是想不起来了。

解析

做法1

设 $f_{t,x}$ 表示 t 时刻在 x 的最大价值。
直接转移即可，时间复杂度 $O(T(n+m))$，期望得分 40 分。
结合无脑转圈的 A 性质，可得 50 分。

做法2

数据范围把矩阵快速幂写脸上了。
每条边建出对应时间个点转移，时间复杂度 $O((5m{)}^{3}k\log T)$，期望得分 65-75 分。

做法3

发现点比较少，边比较多，每条边都分裂节点很蠢。
于是改成把每个点分裂成5个，时间复杂度 $O((5n{)}^{3}k\log T)$。
期望得分没变，乐。

然后？然后就不会了！
。。。
回家种地吧

正解

预处理出转移矩阵 $2^k$ 次，节日之间只需要用行向量乘转移矩阵即可。
时间复杂度 $O((5n{)}^3\log T+(5n{)}^{2}k\log T)$，期望得分 100 分。
这个优化这篇博客写过了，然而就是没有想到，乐。
这甚至根本不能叫优化，就是个写法。
乐。
跳出刻板思维！

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")

inline ll read() {
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-') f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=255;
const int mod=998244353;
const ll inf=-1e18;

bool mem1;

bool Flag=0;

inline ll ksm(ll x,ll k){
    
  ll res(1);
  x%=mod;
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m,T,k;
int tot;
int id[N][6];

struct matrix{
    
  int x,y;
  ll a[N][N];
  matrix(int X=0,int Y=0):x(X),y(Y){
    memset(a,-0x3f,sizeof(a));}
}tr,mi[40],res;
matrix operator * (const matrix &u,const matrix &v){
    
  matrix res(u.x,v.y);
  assert(u.y==v.x);
  for(int k=1;k<=u.y;k++){
    
    for(int i=1;i<=u.x;i++){
    
      ll tmp=u.a[i][k];
      for(int j=1;j<=v.y;j++){
    
	res.a[i][j]=max(res.a[i][j],tmp+v.a[k][j]);
      }
    }
  }
  return res;
}
int c[N];
struct node{
    
  int t,x,w;
  bool operator < (const node &oth)const{
    return t<oth.t;}
}o[N];
int num;

bool mem2;
signed main(){
    
  #ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
  #endif
    
  n=read();m=read();T=read();k=read();
  memset(tr.a,-0x3f,sizeof(tr.a));
  tr.x=tr.y=n*5;
  for(int i=1;i<=n;i++){
    
    for(int j=1;j<=5;j++) id[i][j]=++tot;
    for(int j=1;j<=4;j++) tr.a[id[i][j]][id[i][j+1]]=0;
  }
  for(int i=1;i<=n;i++) c[i]=read();
  for(int i=1;i<=m;i++){
    
    int x=read(),y=read(),w=read();
    tr.a[id[x][w]][id[y][1]]=c[y];
  }
  for(int i=1;i<=k;i++){
    
    int t=read(),x=read(),w=read();
    o[++num]=(node){
    t,x,w};
  }
  o[++num]=(node){
    T,1,0};
  sort(o+1,o+1+num);
  mi[0]=tr;
  for(int i=1;i<=30;i++) mi[i]=mi[i-1]*mi[i-1];
  res.x=1;res.y=tot;
  memset(res.a,-0x3f,sizeof(res.a));
  res.a[1][id[1][1]]=c[1];
  int pre(0);
  for(int i=1;i<=num;i++){
    
    int d=o[i].t-pre;
    for(int k=30;k>=0;k--){
    
      if(d&(1<<k)) res=res*mi[k];
    }
    res.a[1][id[o[i].x][1]]+=o[i].w;
    pre=o[i].t;
  }
  if(res.a[1][id[1][1]]<0) puts("-1");
  else printf("%lld\n",res.a[1][id[1][1]]);
  return 0;
}
/* */