用C++代码写一个区间dp的模板

以下是一个简单的区间dp的模板，使用C语言编写：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

int dp[MAXN][MAXN];

int main() {
    int n;
    scanf("%d", &n);

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

    // 初始化dp数组
    for (int i = 0; i < n; i++) {
        dp[i][i] = a[i];
    }

    // 递推计算dp数组
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = dp[i][i] + dp[i+1][j];
            for (int k = i+1; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }

    // 输出结果
    printf("%d\n", dp[0][n-1]);

    return 0;
}

这个模板可以用来解决一些区间dp问题，例如最长回文子序列、最大子段和等问题。