[NOI2020]美食家题解

题意分析

给出一个带权有向图，要求从节点 $1$ 出发，经过恰好 $T$ 的边权和，回到节点 $1$ ，求可经过的最大点权和。特别地，经过的边权和达到部分特殊数时，会有某个点的点权发生改变。

思路分析

朴素算法

时间复杂度： $O(mT)$
理论得分： $40pts$

设 $f_{i,j}$ 表示在节点 $j$ ，经过的边权和为 $i$ 时可经过的最大点权和。很容易可以得出 DP 方程：

$$f_{i,j}=\max_{(x,j)\in E}(f_{i-val(x,j),x})+c_j$$

暴力转移，点权改变的情况特判修改即可。

优化1

时间复杂度： $O(125n^3k\log T)$
理论得分：$75pts$

可以发现 $w$ 的数据范围很小，想到用矩阵快速幂优化。

首先拆点，令所有边边权都为 $1$ ，然后将所求的点权转化为边权：设有 $(u,v,w)\in E$ ，则可以将 $u$ 拆成 $u_0,u_1,...,u_{w-1}$ ，从 $u_{i-1}$ 向 $u_i$ 间连一条边，边权为 $0$ ，然后从 $u_{w-1}$ 向 $v$ 连一条边，边权为 $c_v$ 。

这样，问题就转化为，从节点 $1$ 出发，经过 $T$ 条边，回到节点 $1$ ，求可经过的最大边权和，即最长路。

定义一个广义矩阵乘法 $ans_{i,j}=max(a_{i,k}+b_{k,j})$ 。可以证明这个广义矩阵乘法同样满足矩阵乘法的基本运算律，如结合律。

设邻接矩阵为 $a$ ，可以很容易得出 DP 方程：

$$dp_i=dp_j*a^{i-j}$$

点权改变的情况怎么处理？只要先将时间从小到大排序，然后在相邻的时间之间转移，转移后在改变点权在邻接矩阵中的对应位置修改即可。

优化2

时间复杂度： $O(125n^3\log T+25n^2k\log T)$
理论得分： $100pts$

分析过后可以发现，因为要求的只是 $dp_{T_{1,1}}$ ，因此只要保留 $dp$ 矩阵的第一行即可；另外，发现在转移的时候要多次乘上邻接矩阵 $a$ 的相同次幂，因此可以先预处理出 $a$ 的 $2$ 的整数次幂。这样处理之后可以降低一维的复杂度。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=300;

const ll INF=0xcfcfcfcfcfcfcfcf;

struct Node

{

    ll p[N][N];

}a[31];

struct Fes

{

    int t,x,y;

    #define t(i) b[i].t

    #define x(i) b[i].x

    #define y(i) b[i].y

}b[N];

int n,m,T,K;

int c[N],id[N][5];

ll dp[N];

Node Max(Node x)

{

    Node now;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            now.p[i][j]=INF;

            for(int k=1;k<=n;k++)

                now.p[i][j]=max(now.p[i][j],x.p[i][k]+x.p[k][j]);

        }

    return now;

}//广义矩阵乘法

void Maxx(Node x)

{

    ll now[N];

    for(int i=1;i<=n;i++)

    {

        now[i]=INF;

        for(int j=1;j<=n;j++)

            now[i]=max(now[i],dp[j]+x.p[j][i]);

    }

    for(int i=1;i<=n;i++)

        dp[i]=now[i];

}//一维乘二维

void pre()

{

    for(int i=1;i<=30;i++)

        a[i]=Max(a[i-1]);

}//预处理次幂

void fastpow(int x)

{

    for(int i=30;i>=0;i--)

        if(x&(1<<i))

            Maxx(a[i]);

}//快速幂

bool cmp(Fes x,Fes y)

{

    return x.t<y.t;

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&T,&K);

    for(int i=1;i<=n;i++)

        scanf("%d",&c[i]),id[i][0]=i;

    memset(a,0xcfcf,sizeof(a));

    for(int i=1,u,v,w;i<=m;i++)

    {

        scanf("%d%d%d",&u,&v,&w);

        for(int j=1;j<w;j++)

        {

            if(!id[u][j])

                id[u][j]=++n;

            a[0].p[id[u][j-1]][id[u][j]]=0;

        }

        a[0].p[id[u][w-1]][v]=c[v];//拆点

    }

    pre();

    for(int i=1;i<=K;i++)

        scanf("%d%d%d",&t(i),&x(i),&y(i));

    sort(b+1,b+K+1,cmp);t(K+1)=T;

    memset(dp,0xcfcf,sizeof(dp));dp[1]=c[1];//初状态

    for(int i=1,d;i<=K+1;i++)

    {

        d=t(i)-t(i-1);

        fastpow(d);

        dp[x(i)]+=y(i);//点权改变

    }//在相邻的时间之间转移

    printf(dp[1]<0?"-1":"%lld",dp[1]);

    return 0;

}

巴特西

[NOI2020]美食家题解

朴素算法

优化1

优化2

最新文章

热门文章

巴特西

[NOI2020]美食家 题解

朴素算法

优化1

优化2

最新文章

热门文章

[NOI2020]美食家题解