Optimal Binary Search Tree

10304 - Optimal Binary Search Tree
Problem E
Optimal Binary Search Tree
Input: standard input
Output: standard output
Time Limit: 30 seconds
Memory Limit: 32 MB
Given a set S = (e1, e2, ..., en) of n distinct elements such that e1 < e2 < ... < en and considering a binary search tree (see the previous problem) of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root.
The cost of accessing an element ei of S in a tree (cost(ei)) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S, (f(e1), f(e2, ..., f(en)), we say that the total cost of a tree is the following summation:
f(e1)*cost(e1) + f(e2)*cost(e2) + ... + f(en)*cost(en)
In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree.

Input

The input will contain several instances, one per line.
Each line will start with a number 1 <= n <= 250, indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), ..., f(en). 0 <= f(ei) <= 100.  Input is terminated by end of file.

Output

For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree.
 

Sample Input

1 5

3 10 10 10

3 5 10 20

 

Sample Output

0

20

20

제목:
가장 좋은 검색 트리, 출력 값을 구성하는 서열을 제공합니다.
아이디어:
처음에 3차원 dp라고 생각했는데 왼쪽, 오른쪽, 층수를 과감하게 TLE를 썼는데 어떻게 개선해야 할지 생각지도 못했고 문제를 보고 문득 깨달았다.
사실 3차원은 없앨 수 있다. 왜냐하면 한 층을 더하기 전에 추가된 권치를 통계할 수 있기 때문이다. 바로 두 구간의 총화이기 때문에 한 층마다 자신의 것만 계산할 필요가 없다.
소감:
어떤 때는 정말 자기가 아무리 생각해도 생각지 못할 때가 있다. 문제풀이를 보면 바로 어떻게 하는지 알 수 있다. 매번 그렇게 조금씩 모자라면 언제쯤 문제풀이를 보지 않고 해낼 수 있을까.
매 문제마다 한 걸음 한 걸음 진정으로 무엇이 바뀌었는지 알 수 있고 그 다음에 어떻게 처리해야 할지 생각해야 한다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 305
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 0.000001
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int a[maxn],sum[maxn];
int dp[maxn][maxn];

int dfs(int le,int ri)
{
    if(le>ri) return 0;
    if(dp[le][ri]!=INF) return dp[le][ri];
    int i,j,t,best=INF;
    for(i=le;i<=ri;i++)
    {
        best=min(best,dfs(le,i-1)+dfs(i+1,ri)+sum[i-1]-sum[le-1]+sum[ri]-sum[i]);
    }
    dp[le][ri]=best;
    return best;
}
int main()
{
    int i,j,t;
    while(~scanf("%d",&n))
    {
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        memset(dp,0x3f,sizeof(dp));
        dfs(1,n);
        printf("%d
",dp[1][n]);
    }
    return 0;
}
/*
1 5
3 10 10 10
3 5 10 20
*/