POJ 1651 Multiplication PuzzleDP方法:

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

有N张写有数字的卡片排成一行，按一定次序从中拿走N-2张（第1张和最后一张不能拿），每次只拿一张，取走一张卡片的同时，会得到一个分数，分值的计算方法是：要拿的卡片，和它左右两边的卡片，这三张卡片上数字的乘积。按不同的顺序取走N-2张卡片，得到的总分可能不相同，求出给定一组卡片按上述规则拿取的最小得分。

DP式子：

dp[L][R] = min(dp[L][R], dp[L][k]+dp[k][R] + a[L]*a[k]*a[R]);

两种方法：

================================================================================

记忆化搜索：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL INF = 0xfffffff;

const LL maxn = ;

int dp[maxn][maxn], a[maxn];

int DFS(int L,int R)

{

    if(dp[L][R])

        return dp[L][R];

    if(R-L <= )

        return ;

    dp[L][R] = INF;

    for(int k=L+; k < R; k++)

        dp[L][R] = min(dp[L][R], DFS(L,k)+DFS(k,R) + a[L]*a[k]*a[R]);

    return dp[L][R];

}

int main()

{

    int n;

    while(cin >> n)

    {

        memset(dp, , sizeof(dp));

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

            cin >> a[i];

        printf("%d\n", DFS(,n));

    }

    return ;

}

/*

6

10 1 50 50 20 5

**/

===================================================================================================

DP方法:

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL INF = 0xfffffff;

const LL maxn = ;

int dp[maxn][maxn], a[maxn];

int main()

{

    int n;

    while(cin >> n)

    {

        memset(dp, , sizeof(dp));

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

            cin >> a[i];

        for(int len=; len <=n; len ++)

        {

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

            {

                int j = i+len;

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

                {

                    if(dp[i][j] == )

                        dp[i][j] = dp[i][k] + dp[k][j] + a[i]*a[j]*a[k];

                    else

                        dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[i]*a[j]*a[k]);

                }

            }

        }

        cout << dp[][n] << endl;

    }

    return ;

}

/*

6

10 1 50 50 20 5

**/