POJ1651：Multiplication Puzzle—

http://poj.org/problem?id=1651

题目大意：同“乘法游戏”，这里将乘法游戏的题面复制过来。

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。你的目标是使得分的和最小。

———————————————————————————————————

太水了……

（其实是以前做过，所以觉得水……）

dp[i][j]表示i～j区间做乘法游戏得到的最小值。

显然长度为3的时候别无选择只能拿中间的。

那么剩下的情况可以为：枚举最后拿的数，递归左右边，最后显然乘起来的就是左右边界和最后的这一个数。

#include<cstdio>

using namespace std;

int a[];

int dp[][]={};

const int INF=;

int main(){

    int n;

    scanf("%d",&n);

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

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

        dp[i][i+]=;

    }

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

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

    }

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

        for(int j=;j<=n-i;j++){

            dp[j][j+i]=INF;

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

                if(dp[j][j+i]>dp[j][k]+dp[k][j+i]+a[j]*a[k]*a[j+i])

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

            }

        }

    }

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

    return ;

}

巴特西

POJ1651：Multiplication Puzzle——题解

最新文章

热门文章