题目分析

本题要求通过给定的 $N$ 块砖（按顺序给出长度 $d_i$），按照特定规则构建一个砖墙，使得墙的“美丽度”（即被四个砖块共顶点的顶点个数）最大。

关键观察

$1$. 砖墙构建规则：

第 $1$ 行：从左到右放置砖块

第 $2$ 行：从右到左放置砖块，右端对齐

第 $3$ 行：从左到右放置砖块，左端对齐

以此类推，方向交替，且相邻行首尾对齐

$2$. 美丽度的含义：

一个顶点被四个砖块共享，意味着在二维平面上，该点是两个垂直砖缝的交点：

垂直砖缝：两行之间的分隔

水平砖缝：同行内两块砖之间的接缝

$3$. 问题的转化：

实际上，美丽度等于层数减一（即行数减一），因为每相邻两行之间最多只能有一个共享顶点。问题转化为：如何划分砖块序列，使得形成的层数最多。

$4$. 约束条件：

每层由若干连续的砖块组成。设第 $i$ 层包含砖块 $[l_i, r_i]$，其总长度为 $S_i$。根据构建规则：

奇数层（从左到右）：$S_i = S_{i-1}$（与上一层总长度相等）

偶数层（从右到左）：$S_i = S_{i-1}$（与上一层总长度相等）

因此，相邻层的总长度必须相等。

算法思路

$1$. 动态规划定义：

定义 $dp[i][j]$ 表示考虑到第 $i$ 块砖，最后一段（当前层）以第 $j$ 块砖结束时，能获得的最大美丽度（层数）。

$2$. 状态转移：

设当前层为 $[k+1, j]$，总长度为 $sum = \sum_{t=k+1}^{j} a[t]$。

要找前一层 $[p+1, k]$，使得其总长度也等于 $sum$。

转移方程：

其中 $p$ 是满足 $\sum_{t=p+1}^{k} a[t] = sum$ 的最大下标。

$3$. 预处理优化：

为了快速找到这样的 $p$，我们需要预处理：

pos[i][j]：对于区间 $[i, j]$，找到最大的 $p < i$ 使得 $[p+1, i-1]$ 的总长度等于 $[i, j]$ 的总长度

g[i][j]：区间 $[i, j]$ 内有多少个前缀和等于某个后缀和（用于辅助计算）

$4$. 实际实现技巧：

代码中使用了二维 DP 数组，但实际有效的状态是 $dp[i][j]$ 其中 $i \le j$。通过维护 pos 数组和 g 数组，可以高效地进行转移。

算法步骤

$1$. 输入处理：

读取 $N$ 和砖块长度数组 $a[1..N]$。

$2$. 三重循环计算：

外层循环：$i$ 从 $1$ 到 $N$，表示当前考虑的前一层结束位置 中层循环：$j$ 从 $i$ 到 $N$，表示当前层结束位置 内层循环：通过指针 $p$ 查找满足长度相等的更早的层

$3$. 状态转移细节：

初始化 $dp[i][j] = dp[i-1][i-1]$

计算当前层 $[i, j]$ 的总长度 $sum$

找到 $p$ 使得 $[p+1, i-1]$ 的总长度等于 $sum$

如果找到匹配的 $p$，尝试转移：$dp[i][j] = \max(dp[i][j], dp[p][i-1] + g[i][j-1] + 1)$

同时考虑不开始新层的情况：$dp[i][j] = \max(dp[i][j], dp[i][j-1], dp[i-1][j])$

$4$. 输出结果：

最终答案为 $dp[N][N]$，即考虑所有砖块时的最大层数减一（美丽度）。

时间复杂度

时间复杂度：$O(N^2)$，因为有三重循环，但内层指针 $p$ 是单调移动的，均摊 $O(1)$

空间复杂度：$O(N^2)$，用于存储 $dp$、$g$、$pos$ 数组

对于 $N \le 5 \times 10^3$，$N^2 = 2.5 \times 10^7$ 在合理范围内。

正确性证明

$1$. 问题等价性：

美丽度等于层数减一，因此最大化美丽度等价于最大化层数。

$2$. 长度相等约束：

由于砖墙的构建规则要求相邻层总长度相等，否则无法对齐边缘。

$3$. 动态规划的最优子结构：

最优解的最后几层必然也是最优的。如果 $[i, j]$ 作为最后一层，那么前面部分 $[1, i-1]$ 必须划分成若干层，且倒数第二层长度必须等于 $[i, j]$ 的长度。

$4$. 转移的完备性：

通过枚举所有可能的 $i, j$ 组合，并利用 pos 数组快速找到匹配的前一层，确保考虑了所有可能的划分方式。

代码实现详解

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

const int N = 5e3 + 5;
int a[N], dp[N][N], g[N][N], pos[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 动态规划计算
    for (int i = 1; i <= n; i++) {
        int sum = 0;  // 当前层[i,j]的总长度
        int pre = 0;  // 前一层[p+1,i-1]的总长度
        int p = i - 1;  // 指针，向左移动
        
        for (int j = i; j <= n; j++) {
            // 初始化
            dp[i][j] = dp[i-1][i-1];
            g[i][j] = g[i][j-1];
            sum += a[j];
            
            // 移动p指针，使pre接近sum
            while (p > 0 && pre + a[p] <= sum) {
                pre += a[p];
                p--;
            }
            
            // 如果找到长度相等的层
            if (sum == pre) {
                g[i][j]++;  // 增加匹配计数
            }
            
            pos[i][j] = p;  // 记录位置
            
            // 状态转移
            if (pos[i][j-1] > 0) {
                // 使用[i,j-1]作为最后一层，尝试转移
                dp[i][j] = max(dp[i][j], dp[pos[i][j-1]][i-1] + g[i][j-1]);
            }
            
            // 考虑不选当前砖块的情况
            dp[i][j] = max(dp[i][j], dp[i][j-1]);
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    
    cout << dp[n][n] << endl;
    return 0;
}