题解：P3016 [USACO11FEB] The Triangle S

_zjy__ · 2025-11-29 11:18:17 · 题解

思路

这题是一道非常经典的纯模拟题。

我们可以先枚举三角形的顶点，再枚举每个三角形的边长！但是 1\le K\le N\le 700，1\le K\le 20，很容易爆掉，所以我们需要优化：

我们要另开一个 prefix 二维数组，来记录每行的前缀和（有名的空间换时间），之后就可以用 O(1) 的时间复杂度通过本题！

本题很像动态规划啊~

CODE

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
//也可换成#include<bits/stdc++.h>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<long long>> triangle(N + 1, vector<long long>(N + 1, 0));
    vector<vector<long long>> prefix(N + 2, vector<long long>(N + 2, 0));
    // 读取三角形数据
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    // 计算前缀和，用于快速计算子三角形和
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            prefix[i][j] = triangle[i][j] + prefix[i][j-1];
        }
    }
    long long result = LLONG_MIN;
    // 枚举所有可能的子三角形
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            // 正朝向的子三角形
            long long sum = 0;
            for (int size = 1; size <= min(N - i + 1, i - j + 1); size++) {
                if (size >= K) {
                    // 计算当前子三角形的和
                    sum = 0;
                    for (int k = 0; k < size; k++) {
                        sum += prefix[i + k][j + k] - prefix[i + k][j - 1];
                    }
                    result = max(result, sum / size);
                }
            }
            // 倒朝向的子三角形
            sum = 0;
            for (int size = 1; size <= min(i, j); size++) {
                if (size >= K) {
                    // 计算当前倒三角形的和
                    sum = 0;
                    for (int k = 0; k < size; k++) {
                        sum += prefix[i - k][j] - prefix[i - k][j - k - 1];
                    }
                    result = max(result, sum / size);
                }
            }
        }
    }

    cout << result << endl;//完美输出
    return 0;
}