[NOI2020] 美食家 题解

本文主要是介绍[NOI2020] 美食家 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

之前一直对这题有点迷惑，现在终于搞懂了，故作此文。

upd：昨天晚上写的没保存，今天重新写，悲（ 。

难度

大概 \(2500\) ，思路比较自然，使用的都是常用优化技巧。

题意简述

给定一个 \(n\) 个点， \(m\) 条边的有向图，走过每条边需要花费 \(w_i\) 天，每个点有一个得分 \(c_i\) 。

另外有 \(k\) 个活动，第 \(i\) 个活动表示如果在第 \(t_i\) 天走到点 \(x_i\) ，你可以获得 \(y_i\) 的加分。

找到一条从 \(1\) 开始，在 \(1\) 结束的回路，消耗的天数恰好是 \(T\) ，最大化你的得分。

\(1 \le n \le 50\) ， \(1 \le m \le 501\) ， \(1 \le k \le 200\) ，\(1 \le t_i \le T \le 10^9\) ，保证 \(t_i\) 两两不同。

Solution

从暴力入手，如果纯 \(dfs\) 搜索每条可能路径，复杂度指数级，期望得分 \(20\) 分。

你发现一个比较显然的 \(DP\) 是，设 \(dp[i][j]\) 表示走了 \(i\) 天，走到 \(j\) 点的最大得分，走到天数多的情况由天数少的情况转移而来，显然没有后效性，只需枚举上一条到达该点的边即可转移。

设枚举的边是 \((k,j,w)\) 转移方程大概是这样： \(dp[i][j]=max(dp[i-w][k])+c_i\) 。

时间复杂度 \(O(Tn)\) ，期望得分 \(40\) 分。

你发现 \(T\) 非常大，而点数比较小，这个范围一般都会想到矩阵快速幂来优化 \(DP\) 。

你发现在尝试矩阵时遇到很多问题，乘上一个转移矩阵一般是从 \(f[i]\) 转移到 \(f[i+1]\) ，而此处是 \(i+w\) ，那你发现 \(w_i\) 最大是 \(5\) ，那你首先肯定考虑拆边，拆成长度条边，那你这样的话，就可以利用“邻接矩阵的 \(T\) 次方可以表示走出 \(T\) 步”的这一性质了。

当前矩乘想求的是最大得分，而不是有多少条路径，所以要重新定义邻接矩阵，矩阵乘法转移的是这个最大得分的值，所以边权定义为到达的那个点的点权(如果是拆出来的边，则为 \(0\) ) 。

你发现这个 \(m\) 确实比较大，这样矩阵乘法是 \((n+4m)^3\) ，如果拆边就很慢了，考虑拆点，怎么拆？

把一个点 \(x\) 拆成五个点 \(x[1~5]\) ,那这五个点肯定先连成链，然后对于一条边 \((u,v,w)\) ，从 \(u_w\) 连向 \(v_1\) ，边权是到达那个点的点权。

你发现还要最大化得分，那就得重新定义矩阵乘法，设 \(G\) 是重定义的邻接矩阵，看看现在的方程。

\(dp[i+1][j]=max(dp[i][k]+G[k][j])\)

是不是很像原矩阵乘法的 \(C[i][j]+=A[i][k] \times B[k][j]\) ，那现在矩阵乘法就定义成 \(C[i][j]=max(A[i][k]+B[k][j])\) ，符合方程形式。

那现在就可以直接求矩阵的次幂了， \(dp[T]=dp[1] \times G^T\) 。

然后你发现还有 \(k\) 个活动，没关系，按时间排序，分段求幂，每次求 \(t_i-t_{i-1}\) 次幂，然后 \(dp[t_i][x_i]+=y_i\) 即可。

时间复杂度 \(O(k(5n)^3logT)\) ，期望得分 \(75\) 分。

这时候你发现这个 \(dp\) 矩阵其实只需要存 \(n\) 个点的信息，那就是说是个 \(1 \times n\) 的矩阵，所以递推 \(dp\) 的矩阵乘法只需要 \(O((5n)^2)\) 。但是邻接矩阵 \(G\) 每次还是 \((5n)^3\) 的，这时候再用一个矩乘优化技巧，因为每次乘上的都是固定矩阵 \(G\) 的某一次幂，预处理 \(G\) 的 \(2\) 的次幂，的次幂，也就是预处理 \(G^1,G^2,G^4.....\) 即可。

预处理复杂度 O((5n)^3logT) ，转移复杂度 \(O(k(5n)^2logT)\) ，期望得分 \(100\) 分。

总结

这题用到了很多矩阵的优化技巧，比如说预处理二进制次幂，注意 \(1 \times n\) 矩阵等等，是一道好题。

#include<bits/stdc++.h>
#define ll long long
#define N 55
#define M 505
#define inf 1e15
using namespace std;
int cnt,n,m,k,T,a[N],id[N][6],A,B,C,u[M],v[M],w[M];
ll d;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node
{
	ll m[5*N][5*N];
}dp,G[31];
struct fes
{
	int t,x;
	ll y;
}b[M];
int cmp(fes x,fes y)
{
	return x.t<y.t;
}
node mul(node x,node y)
{
	node z;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=cnt;j++) z.m[i][j]=-inf;
	}	
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			for(int k=1;k<=cnt;k++) z.m[i][j]=max(z.m[i][j],x.m[i][k]+y.m[k][j]);
		}
	}
	return z;
}
void merge(node x,node y)
{
	ll z[5*N];
	for(int i=1;i<=cnt;i++) z[i]=-inf;
	for(int k=1;k<=cnt;k++)
	{
		for(int i=1;i<=cnt;i++) z[i]=max(z[i],x.m[1][k]+y.m[k][i]);
	}
	for(int i=1;i<=cnt;i++) dp.m[1][i]=z[i];
}
int main()
{
	n=read();m=read();T=read();k=read();
	for(int i=1;i<=n;i++) a[i]=read(),id[i][0]=i;
	cnt=n;	
		
	for(int i=1;i<=m;i++)
	{
		u[i]=read();v[i]=read();w[i]=read();
		A=u[i];B=v[i];C=w[i];
		for(int j=1;j<=C-1;j++) 
		{
			if(!id[A][j]) id[A][j]=++cnt;
		}
	}
	for(int i=0;i<=30;i++) 
	{
		for(int j=0;j<=cnt;j++)
		{
			for(int k=0;k<=cnt;k++) G[i].m[j][k]=-inf;
		}
	}
	for(int i=1;i<=m;i++)
	{
		A=u[i];B=v[i];C=w[i];
		for(int j=1;j<=C-1;j++) G[0].m[id[A][j-1]][id[A][j]]=0;
		G[0].m[id[A][C-1]][B]=a[B];
	}
	for(int i=1;i<=k;i++)
	{
		b[i].t=read();b[i].x=read();b[i].y=read();
	}
	b[++k].t=T;
	sort(b+1,b+k+1,cmp);
	for(int i=1;i<=30;i++) G[i]=mul(G[i-1],G[i-1]);
	for(int i=1;i<=cnt;i++) dp.m[1][i]=-inf;
	dp.m[1][1]=a[1];
	for(int i=1;i<=k;i++)
	{
		d=b[i].t-b[i-1].t;
		for(int j=0;j<=30;j++)
		{
			if((d>>j)&1) merge(dp,G[j]);
		}
		dp.m[1][b[i].x]+=b[i].y;
	}
	if(dp.m[1][1]<0) printf("-1");
	else printf("%lld",dp.m[1][1]); 
	return 0;
}   

这篇关于[NOI2020] 美食家 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！