题解：P3016 [USACO11FEB] The Triangle S

原题链接

• 洛谷 P3016 [USACO11FEB] The Triangle S

解题思路

枚举所有的等边三角形，利用前缀和优化求和。

将正的三角形和倒的三角形分开计算。

枚举三角形的顶点 $(i,j)$，边长为 $k$ 的等边三角形。（$j\le i$）

对于每个边长为 $k$ 的三角形：

1. 总和可以由边长为 $k-1$ 的三角形的总和加上第 $k$ 行，而第 $k$ 行可以用前缀和计算。
2. 数字个数为 $\frac{k(k+1)}{2}$。
3. 如果 $K\le k\le 2K$，计算平均值，并维护最大值。

时间复杂度 $O(n^2k)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=705;
ll a[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,K;
	cin>>n>>K;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
			a[i][j]+=a[i][j-1];
		}
	}
	ll ans=-inf;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			ll sum=0;
			for(int k=1;k<=n-i+1;k++)
			{
				sum+=a[i+k-1][j+k-1]-a[i+k-1][j-1];
				if(k<K)continue;
				if(k>K*2)break;
				ans=max(ans,sum/(k*(k+1)/2));
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			ll sum=0;
			for(int k=1;k<=j&&k<=i-j+1;k++)
			{
				sum+=a[i-k+1][j]-a[i-k+1][j-k];
				if(k<K)continue;
				if(k>K*2)break;
				ans=max(ans,sum/(k*(k+1)/2));
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}