【kuangbin带你飞-区间DP-3】E – Multiplication Puzzle POJ-1651动态规划,算法,c++wuhuaqing20151637的博客-

题目链接：(https://poj.org/problem?id=1651)

题目大意

给你一个卡片数组，每个卡片都带有一个正整数。现在让你从卡片数组中那卡片，每次拿一个不放回，每次拿的时候的得分是该卡片的数和左右两边卡片数之积。且卡片的开头和结尾不允许拿走，问你这样操作，最后之剩首尾两张卡片的时候，最小的得分是多少。

Input

The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer – the minimal score.

Sample Input

6
10 1 50 50 20 5

Sample Output

3650

思路：

这是典型的区间dp，考虑最后以一种情况，数组a[]除了首尾，只剩下一个卡片k，那么这时候的得分肯定是a[k]*a[l]*a[r]+消去 l~k 中间卡片的得分+消去k~r中间的卡片的得分。
因此我们可以设置dp状态dp[l][r]表示消去区间【l,r】中间的元素（不包含首尾）的得分，那么最后的答案为dp[0][n-1]

状态转移方程

dp[l][r] = min {dp[l][k]+dp[k][r]+a[k]*a[l]*a[r]},l<k<r
注意边界条件，长度小于等于2的区间dp[l][r]=0
其他情况，dp[l][r]初始值为无穷大

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 200; const int inf = 0x3f3f3f3f; int dp[maxn][maxn]; int a[maxn]; int main() {     ios::sync_with_stdio(false);//优化 int n;     cin >> n; for(int i = 0; i < n; i++)         cin >> a[i]; memset(dp, inf, sizeof(dp)); for(int i = 0; i < n; i++) {         dp[i][i] = 0; if(i < n - 1)             dp[i][i + 1] = 0; } for(int len = 3; len <= n; len++) { for(int l = 0; l + len <= n; l++) { int r = l + len - 1; for(int k = l + 1; k < r; k++) {                 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[k] * a[l] * a[r]); } } }     cout << dp[0][n - 1] << endl; }