UVA10304---(区间DP)

第一开始想着枚举根节点，然后记忆化搜索。。结果TLE，最后还是看了一眼题解瞬间明白了。。唉，还是思维太局限了

由于数据是按照从小到大排列的，可以自然地组成一颗二叉排序树。

设dp[i][j]是区间[i,j]的元素可以组成的BST的最小值，则大区间的结果和根节点以及小区间的结果有关系，很明显区间DP，

转移方程搭dp[i][j] = min{dp[i][k-1] + dp[k+1][j] + sum(i,j) - a[k]} sum(i,j)是区间和，因为当把两棵左右子树连在

根节点上时，本身的高度增加1，所以每个元素都多计算一次，最后根节点由于层数是0，所以还要减去根节点。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<sstream>
#include<queue>
#include<stack>
#define INF 530600414
#define N 201314
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int maxn = 255;

int n;
int a[maxn];
int dp[maxn][maxn];
int sum[maxn];

int main()
{
    //freopen("in","r",stdin);
    while(~scanf("%d",&n)) {

        sum[0] = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        //sort(a+1,a+n+1);

        if(n == 1) dp[1][n] = 0;
        else {
            memset(dp,0,sizeof(0));
            //for(int i = 1; i <= n; ++i) dp[i][i] = a[i];

            for(int l = 2; l <= n; ++l)
                for(int st = 1; st+l-1 <= n; ++st) {
                    int ed = st+l-1;
                    dp[st][ed] = INF;
                    int cnt = sum[ed]-sum[st-1];
                    for(int k = st; k <= ed; ++k)
                        dp[st][ed] = min(dp[st][ed],dp[st][k-1] + dp[k+1][ed] + cnt - a[k]);
                }
        }
        printf("%d
",dp[1][n]);
    }
}