题目描述 给定一个数组，要求将这个数组划分成若干段，使得 ∑ i = 1 k sum i ∗ i 最大， k 是划分之后的段数。 输入格式 第一行输入一个 n 表示数组元素个数； 第二行输入 n 个数，表示数组中的数。 输出格式 输出一个整数表示答案。

这个问题是一个优化问题，可以通过动态规划（Dynamic Programming）来求解。我们需要找到分割数组的方式，使得每一段的平方和乘以其索引之和最大。这个问题可以用一个二维数组 `dp` 来记录状态，其中 `dp[i][j]` 表示前 `i` 个元素分割为 `j` 段的最大总和。

算法步骤如下：

1. 初始化：`dp[0][0] = 0`，因为没有元素时，无论分多少段都得0。对于单个元素 `a[0]`，分成1段的总和就是 `a[0]^2 * 1`，所以 `dp[1][1] = a[0]^2`.

2. 填充状态：遍历数组，从 `i=1` 到 `n`，对每个元素 `a[i]` 和每可能的段数 `j`，计算两种情况的总和：保持当前段数不变，即 `dp[i][j] = dp[i-1][j] + a[i]^2 * i`；增加一段，即 `dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + a[i]^2 * i)`。

3. 返回结果：最终的结果是 `dp[n][k]`，其中 `k` 是最大的分割段数，但要注意实际情况下数组不能被无限分割，所以我们通常取不超过数组长度的一半作为 `k` 的上限。

这是一个典型的二维动态规划问题，你需要编写如下的 C 代码：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int dp[n+1][n/2+1]; // 取上限n/2，因为我们不会使用超过一半的段
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][1] = dp[i-1][1] + arr[i-1] * arr[i-1] * i;
        for (int j = 2; j <= n/2; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + arr[i-1] * arr[i-1] * i);
        }
    }

    int ans = dp[n][n/2];
    printf("%d\n", ans);

    return 0;
}