[POJ - 1651] Multiplication Puzzle

发表于 | 更新于 | 分类于 ， ，
本文字数： 10k

链接

\(\text{POJ - 1651 Multiplication Puzzle}\)

题意

   给你一个长度为\(n\)的序列\(a\)，现在你将要把，序列\(a\)中除开头和结尾外的所有元素都删除掉,你每次删除一个数\(a_i\)时，你将会得到的分数为\(a_{i-1}*\)\(a_i*a_{i+1}\)，你需要获得最少的分数，问这个分数最小为多少。

  比如对于序列\({10,1,50,20,5}\)，你依次删除\(50、20、1\)，得到的分数分别为\(1*50*20、1*20*5、10*1*5\)，总共为\(1150\)，这样你就能获得最少的分数。

分析

  这是一道区间\(\text{DP}\)题目，依旧是枚举区间长度与起点，求出小区间的最优决策，然后得到大区间的解。状态转移方程为：\[dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])\]

  \(dp[i][j]\)即为区间\([i,j]\)所能获得的最小分数。

  另外，如果是获得最大分数，只需要将数组初始化为0即可。

  区间\(dp\)一般基本套路即是枚举区间长度与起点，然后求接小区间解，进而合并得到大区间的解，关键是转移方程。

区间\(dp\)基本模板

1
2
3
4
5
6
7
8
for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

int n, dp[130][130], a[120];
int main() {
	cin >> n;
	memset(dp, INF, sizeof(dp));
	for (int i = 1; i <= n; i++)
		cin >> a[i],dp[i][i] = dp[i - 1][i] = 0;
	for (int len = 2; len <= n; len++)
		for (int i = 1; i + len - 1 <= n; i++) {
			int j = i + len - 1;
			for (int k = i + 1; k < j; k++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]+ a[i] * a[k] * a[j]);
		}
	cout << dp[1][n] << endl;
}