NOI真题解答201

赵思铭 · 2022-07-10 20:15:58 · 个人记录

本题与矩阵乘法有关，考虑矩阵乘法的性质，需满足乘法交换律与加乘结合律，（加法交换律可由这两个定律推出）

在本题中，取max为广义加法，加法为广义乘法，定义矩阵乘法，考虑分5层建图

考虑对矩阵预处理，不过还是kn^3,最后只需要第一行的矩阵，这样从最左边开始，只保留第一行，每次只需n^2,一共有k段，每两段之间二进制拆分，kn^2log(n)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=255;
const int inf=0x3f3f3f3f3f3f3f3fll;
int n;
struct M{
    int d[N][N];
    M operator*(const M &R)const {
        M ret;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            ret.d[i][j]=-inf;
            for(int k=1;k<=n;k++)
                ret.d[i][j]=max(ret.d[i][j],d[i][k]+R.d[k][j]);
        }
        return ret;
    }
}X[35],G;
int T,K;
int c[N];
int t[N],x[N],y[N];
int b[N],tmp[N];
int m;
void mul(M Y) {
    for(int i=1;i<=n;i++) {tmp[i]=b[i];b[i]=-inf;}
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            b[i]=max(b[i],tmp[j]+Y.d[j][i]);
        }
}
signed main() {
    cin>>n>>m>>T>>K;
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=5*n;i++)
    for(int j=1;j<=5*n;j++)
        X[0].d[i][j]=-inf; 
    for(int i=1;i<=n;i++)
    for(int j=1;j<=4;j++)
        X[0].d[i+n*j][i+n*(j-1)]=0;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        X[0].d[v][u+n*(w-1)]=c[v];
    }
    n*=5;
    for(int i=1;i<=30;i++) X[i]=X[i-1]*X[i-1];
    for(int i=1;i<=K;i++) scanf("%lld%lld%lld",&t[i],&x[i],&y[i]);
    for(int i=1;i<=K;i++)
    for(int j=i+1;j<=K;j++) {
        if(t[i]<t[j]) {
            swap(t[i],t[j]);
            swap(x[i],x[j]);
            swap(y[i],y[j]);
        }
    }
    for(int i=2;i<=n;i++) b[i]=-inf;
    int z=T-t[1];
    for(int k=0;k<=30;k++)
        if((z>>k)&1) mul(X[k]);
    for(int i=1;i<=K;i++) {
        G=X[0];
        for(int j=1;j<=n;j++)
            G.d[x[i]][j]+=y[i];
        mul(G);
        int z=t[i]-t[i+1]-1;
        for(int k=0;k<=30;k++)
        if((z>>k)&1) mul(X[k]);
    }
    cout<<max(c[1]+b[1],-1ll)<<endl;
    return 0;
}