题解：P3016 [USACO11FEB] The Triangle S

· · 题解

解题思路

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

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

对于每个边长为 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;
}