POJ 1651 Multiplication Puzzle （区间dp）-程序员宅基地

题目大意：对n个数组成的序列取数，规定最两边不能取，每次取一个a[i]，得到 a[l] * a[i] * a[r] 的分数(a[l]是a[i]左边的数,a[r]是a[i]右边的数)，并把这个数从序列中移走，求n-2次取数后的得分和的最小值

分析：正着确定状态不好做，不如反着来，设dp[l][r]为向区间[l, r]中填满数所得到分数和的最小值，考虑最近一次填数的位置，不难得出：

dp[l][r] = fmin(dp[l][m] + dp[m][r] + a[l] * a[m] * a[r]) (l<m<r);

实现方式可以选择记忆化递归，也可直接以区间长度为阶段来递推，各有优缺点，代码如下：

/**********************************************
***    Problem:
***    Author:        JKL
***    University:    CSUST
***    Team:          __Dream
***    Email:          [email protected]
***    My Blog:        http://www.cnblogs.com/jklongint/
***********************************************/
//===================================================
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <numeric>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <bitset>
#include <deque>
using namespace std;
//---------------------------------------------------
#define mem(a,b) memset(a,b,sizeof(a))
#define GO cout<<"HelloWorld!"<<endl
#define Case(x) cout<<"Case "<<x<<":"
#define foru(i,n) for(int i=1; i <= n; i++)
#define ford(i,n) for(int i = n; i >= 1; i--)
 #define fin freopen("input.txt","r",stdin);
 #define fout freopen("output.txt","w",stdout)
#define lson  l, m, rt << 1
#define rson  m + 1, r, rt << 1 | 1

#define sqr(a)  ((a)*(a))
#define abs(a) ((a>0)?(a):-(a))
#define pii pair<int,int>

#define fmax(a,b) max(a,b)
#define fmin(a,b) min(a,b)
#define fmax3(a,b,c)  (fmax(a,fmax(a,b)))
#define fmin3(a,b,c)  (fmin(a,fmin(a,b)))

#define sfi(x) scanf("%d",&x)
#define sfL(x) scanf("%I64d",&x)
#define sfc(x) scanf("%c",&x)
#define sfd(x) scanf("%lf",&x)
#define sfs(x) scanf("%s",x)
#define sfii(a,b) scanf("%d%d",&a,&b)
#define sfLL(a,b) scanf("%I64d%I64d",&a,&b)
#define sfcc(a,b) scanf("%c%c",&a,&b)
#define sfdd(a,b) scanf("%lf%lf",&a,&b)
#define sfss(a,b) scanf("%s%s",a,b)

#define pfi(x) printf("%d",x)
#define pfL(x) printf("%I64d",x)
#define pfs(x) printf("%s",x)
#define pfd(x) printf("%lf",x)
#define pfc(x) print("%c",x)
#define newLine pfs("\n")
#define space pfs(" ")

//--------------------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;
typedef __int64 __LL;
typedef unsigned __int64 __ULL;

typedef vector<int> vi;
typedef vector<LL> vL;
typedef vector<string> vs;
typedef set<int> si;
typedef map<int,int> mii;
typedef map<LL,LL> mLL;
typedef map<string,int> msi;
typedef map<char,int> mci;
//--------------------------------------------------------
const int dx[4]={
     1,-1,0,0};
const int dy[4]={
     0,0,1,-1};
 const int day[13]={
     0,31,28,31,30,31,30,31,31,30,31,30,31};
 const int N6=1000006;
 const int N5=100006;
 const int N4=10006;
 const int N3=1006;
 const int N2=106;
 const int N=1009;
 const int MOD=1000000007;
 const LL LMAX=0x7fffffffffffffff;
 const LL IMAX=0x3fffffff;
 const double PI=3.14159265359;
//--------------------------------------------------------
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }

//------------------------------------------------------------
struct TreeNode{
    LL  sum, add;
};
//=================================================================
TreeNode tree[N << 3];
int flag[N][N], a[N], dp[N][N];
int dpSearch(int l, int r)
{
    if(l + 1 == r)return 0;
    if(flag[l][r])return dp[l][r];
    dp[l][r] = IMAX;
    for(int j = l + 1; j < r; j++){
        int s = dpSearch(l, j), t = dpSearch(j, r);
        //if(l == 1 && r == 4)cout<< s<< t<< endl;
        dp[l][r] = fmin(dp[l][r], s + t + a[l] * a[j] * a[r]);
    }
    flag[l][r] = 1;
    //cout<<l<<r<<dp[l][r]<<endl;
    return dp[l][r];
}
int main()
{
    //fin;//fout;//freopen("input.txt","r",stdin);
    int n;
    cin>>n;
    foru(i, n)sfi(a[i]);
    cout << dpSearch(1, n) << endl;
    return 0;
}