UVa 10304 Optimal Binary Search Tree(区間DP)

タイトル:
二叉ルックアップツリーとは何かを理解し、次に最適な二叉ルックアップツリーを理解することを前提とします.
最適二叉ルックアップツリーとは、二叉ルックアップツリーに基づいて、総符号化長が最小(huffman符号化に類似)であることが要求される.
考え方:
非常に複雑に見えますが、実際には多くの細部を捨てて、ルートノードとして、その左右のサブツリーもきっと最適であることがわかります.
この考え方に基づいて,区間動的計画を自然に思い出し,小規模最適解から徐々に拡大することができる.
区間規模が大きくなると、新しいルートノードが選択され、区間にルートノードの左右を除いた最適解に高さが加算され、繰返し式があります.
k1 = max(k - 1, i),k2 = min(k + 1, j); (i <= k <= j) dp[i][j] = min(dp[i][j], dp[i][k1] + dp[k2][j] + sum[j] - sum[i-1] - a[k]);
前提条件は、a[]配列要素が増加/減少の順序を保つことです.
 

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>



#define max(a,b) (((a) > (b)) ? (a) : (b))

#define min(a,b) (((a) < (b)) ? (a) : (b))



const int MAXN = 256;

int dp[MAXN][MAXN];

int a[MAXN], sum[MAXN];



int main()

{

    int n;

    while (scanf("%d", &n) != EOF)

    {

        for (int i = 1; i <= n; ++i)

            scanf("%d", &a[i]);



        sum[0] = 0;

        for (int i = 1; i <= n; ++i)

            dp[i][i] = 0, sum[i] = sum[i-1] + a[i];



        for (int p = 2; p <= n; ++p) 

        {

            for (int i = 1, j = p; j <= n; ++i, ++j) 

            {

                dp[i][j] = INT_MAX;

                for (int k = i; k <= j; ++k) 

                {

                    int k1 = max(k - 1, i);

                    int k2 = min(k + 1, j);

                    dp[i][j] = min(dp[i][j], dp[i][k1] + dp[k2][j] + sum[j] - sum[i-1] - a[k]);

                }

            }

        }

        printf("%d
", dp[1][n]);

    }

    return 0;

}