题解

题目分析

这是一道基于图论和动态规划的题目，需要在四个六边形网格中寻找最长路径。

解题思路

1. 问题建模

• 将四个六边形网格的节点编号并建立图结构
• 每个节点最多连接3个相邻节点
• 需要找到图中的最长路径

2. 图构建

• 使用邻接表存储图结构：w_edge[u][i] 表示节点 $u$ 的第 $i$ 个邻居
• 通过 w_add(u,v) 函数建立双向边
• 处理六边形网格的特殊连接关系

3. 动态规划求解

• 定义状态：$f[u][v][l]$ 表示从节点 $u$ 出发，经过邻居 $v$，在区间 $[l, r]$ 内的最长路径长度
• 状态转移：$f[u][v][l] = \max_{i \neq v} f[neighbor_i][l', u] + f[neighbor_j][r', u] + 1$
• 其中 $l'$ 和 $r'$ 根据 $l$ 和 $r$ 的关系确定

4. 关键技巧

• 使用记忆化搜索避免重复计算
• 通过区间划分处理路径约束
• 枚举每个节点作为起点寻找全局最优解

时间复杂度

$O(n^4)$，其中 $n$ 为六边形网格的层数。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,x,y,w_ans,a[4][25][45],w_edge[4805][15],f[1605][15][1605];
bool g[1605][1605];
void w_add(int u,int v)
{
	if(!g[u][v])
	{
		g[u][v]=1;
		w_edge[u][++w_edge[u][0]]=v;
	}
	if(!g[v][u])
	{
		g[v][u]=1;
		w_edge[v][++w_edge[v][0]]=u;
	}
}
int w_dp(int u,int l,int r)
{
	int v=1;
	while(w_edge[u][v]!=r)
		v++;
	if(f[u][v][l])
		return f[u][v][l];
	int x=0;
	int y=0;
	int l_,r_;
	if(l<=r)
		l_=l,r_=r-1;
	else
		l_=r+1,r_=l;
	for(int i=1;i<=3;i++)
	{
		if(i==v)
			continue;
		if(w_edge[u][i]<l_||w_edge[u][i]>r_)
			continue;
		if(w_edge[u][i]<u)
			x=max(x,w_dp(w_edge[u][i],l_,u));
		else
			y=max(y,w_dp(w_edge[u][i],r_,u));
	}
	return f[u][v][l]=x+y+1;
}
int main()
{
	scanf("%d",&n);
	m=4*n*n;
	for(int i=0;i<4;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=2*j-1;k++)
				scanf("%d",&a[i][j][k]);
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=2;j<n;j++)
		{
			for(int k=2;k<2*j-1;k++)
			{
				w_add(a[i][j][k],a[i][j][k-1]);
				w_add(a[i][j][k],a[i][j][k+1]);
				if(k&1)
					w_add(a[i][j][k],a[i][j+1][k+1]);
				else
					w_add(a[i][j][k],a[i][j-1][k-1]);
			}
		}
		for(int k=2;k<2*n-1;k+=2)
		{
			w_add(a[i][n][k],a[i][n][k-1]);
			w_add(a[i][n][k],a[i][n][k+1]);
			w_add(a[i][n][k],a[i][n-1][k-1]);
		}
	}
	w_add(a[0][1][1],a[1][1][1]);
	w_add(a[0][1][1],a[2][1][1]);
	w_add(a[1][1][1],a[2][1][1]);
	w_add(a[0][n][1],a[3][n][1]);
	w_add(a[0][n][1],a[2][n][2*n-1]);
	w_add(a[3][n][1],a[2][n][2*n-1]);
	w_add(a[0][n][2*n-1],a[3][1][1]);
	w_add(a[0][n][2*n-1],a[1][n][1]);
	w_add(a[3][1][1],a[1][n][1]);
	w_add(a[1][n][2*n-1],a[2][n][1]);
	w_add(a[1][n][2*n-1],a[3][n][2*n-1]);
	w_add(a[2][n][1],a[3][n][2*n-1]);
	for(int i=1;i<=n;i++)
	{
		w_add(a[0][i][2*i-1],a[1][i][1]);
		w_add(a[0][i][1],a[2][i][2*i-1]);
		w_add(a[0][n][2*i-1],a[3][n-i+1][1]);
		w_add(a[1][i][2*i-1],a[2][i][1]);
		w_add(a[1][n][2*i-1],a[3][i][2*i-1]);
		w_add(a[2][n][2*i-1],a[3][n][2*(n-i+1)-1]);
	}
	for(int i=1;i<=m;i++)
	{
		x=0;
		y=0;
		for(int j=1;j<=3;j++)
		{
			if(w_edge[i][j]<i)
				x=max(x,w_dp(w_edge[i][j],1,i));
			else
				y=max(y,w_dp(w_edge[i][j],m,i));
		}
		w_ans=max(w_ans,x+y+1);
	}
	printf("%d",w_ans);
	return 0;
}