【区间DP&&记忆化搜索】乘法游戏

题目描述

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

    你的目标是使得分的和最小。
    例如，如果数是10 1 50 20 5，依次拿1、20、50，总分是                       10*1*50+50*20*5+10*50*5=8000
    而拿50、20、1，总分是1*50*20+1*20*5+10*1*5=1150。 

输入

 输入文件mul.in的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。

输出

 输出文件mul.out只有一个数字：最小得分

样例输入

6
10 1 50 50 20 5

样例输出

3650

思路

记忆化搜索和DP本质是一样的，本题相当于用到了分治的思想，都是由小区间合并成大区间，dp[i][j]表示区间i，j之间的最大值，每次枚举[i,j]之间的断点更新dp[i][j]

值得注意的是初始化的值（-1，0，INF），具体可以看代码qwq

代码

（1） 记忆化搜索

//#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 105,INF=0x3f3f3f3f; 
/*
6 
10 1 50 50 20 5
*/
int n,a[N];
int dp[N][N];
int dfs(int l,int r)
{
    if(r<=l+1) return 0;//!
    if(dp[l][r]!=-1)  return dp[l][r];
    dp[l][r]=INF;
    for(int i=l+1;i<=r-1;i++)
    {
        dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i,r)+a[i]*a[l]*a[r]);
        //    dp[l][r]=min(dp[l][r],dp[l][i]+dp[i][r]+a[i]*a[l]*a[r]);
    }
//    printf("%d\n",dp[l][r]);
    return dp[l][r];
    
}
int main()
{
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    dfs(1,n);
    printf("%d",dp[1][n]);
    return 0;
}

（2）区间DP的三重循环

//#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 105,INF=0x3f3f3f3f; 
/*
6 
10 1 50 50 20 5
*/
int n,a[N];
int dp[N][N];
int main()
{
    scanf("%d",&n);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),dp[i][i+1]=0;
    for(int i=3;i<=n;i++)
    {
        for(int l=1;l+i-1<=n;l++)
        {
            int r=l+i-1;
            dp[l][r]=INF;
            for(int k=l+1;k<=r-1;k++)
            {
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[r]*a[k]);
            }
        }    
    }
    printf("%d",dp[1][n]);
    return 0;
}