原题链接题意： 给你一个长为 N 的数字序列，其中序列中的值范围在\((1~100)\)。你需要每次在序列中抽取一个数字（不能抽取两端），每次抽取一个数字的花费为：抽取的数字与其左右数字的乘积。 当你把牌抽到只剩下左右两端时，求出能得到的最小花费。思路： 区间dp的思路即是：为了解在一个区间上的最优解，那么把这个区间分割成一个个小区间，求解每个小区间的最优解。所以我们设二维\(dp[i][j]\)$ 表示从\(i\)开始到\(j\)结束的区间段 (我们可以认为这里的区间即表示区间\((i~j)\)之间的值已经被抽取完了，只剩下端点和中间位置） 初始化：我们先对第一步抽取的值进行初始化，即\(dp[i][i+2]=arr[i]\times arr[i+1]\times arr[i+2]\) 之后我们再对大的区间进行分割 \(dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+arr[i]*arr[k]*arr[j])\), 即新的更大的区间由两个端点以及其 中间值乘积组成 所以根据以上的状态转移方程可以求解code:
#include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #define IOS ios::sync_with_stdio(0); cin.tie(0); #define mp make_pair #define Pi acos(-1.0) #define accept 0 using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; const int maxn = 1e3+7; const int maxm = 1e6+7; const int mod = 1e9+7; int arr[maxn]; int dp[maxn][maxn]; int main(){ int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); } memset(dp,0,sizeof(dp)); for(int i=1;i<n-1;i++) dp[i][i+2] = arr[i]*arr[i+1]*arr[i+2];//先初始化连续三个位置 for(int len=4;len<=n;len++){ //s为起点，e为终点,len为区间长度 for(int s=1;s+len-1<=n;s++){ int e = s+len-1; dp[s][e] = inf; for(int k = s+1;k<e;k++){ dp[s][e] = min(dp[s][e],dp[s][k]+dp[k][e]+arr[s]*arr[k]*arr[e]); } } } printf("%d\n",dp[1][n]); } }转载于:https://www.cnblogs.com/Tianwell/p/11424613.html
