题目传送门
Description
The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.
The goal is to take cards in such order as to minimize the total number of scored points.
For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring
10150 + 50205 + 10505 = 500+5000+2500 = 8000
If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be
15020 + 1205 + 1015 = 1000+100+50 = 1150.
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：用dp[i][j]表示区间(数组下标)ij之间所有数字全部抽出后的最小费用（最后留下i和j）；k表示ij之间最后一个抽出的数字。
则有状态转移方程 dp[i][j] = min{dp[i][j] , dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]} 就是找到区间i ~ j之间最后一个取出哪个数字费用最小。
其中区间i ~ k和区间k ~ j之间的最小费用都已经算出，所以直接加上最后一次取出k的费用a[i]*a[k]*a[j]就是当前的总费用。 - 记忆化搜索
AC-Code：
- DP:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <fstream>
#include <utility>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;const int INF = 0x7fffffff;
const int MAXN = 710;
const int MOD = 1e9 + 7;int a[MAXN];
int dp[MAXN][MAXN];int main() {
int n;while (cin >> n) {
memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++)cin >> a[i];for (int len = 3; len <= n; len++) {
for (int i = 1; i <= n; i++) {
int j = i + len - 1;if (j > n)break;dp[i][j] = INF;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;}return 0;
}
- 记忆化搜索
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <fstream>
#include <utility>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;const int INF = 0x7fffffff;
const int MAXN = 710;
const int MOD = 1e9 + 7;int a[MAXN];
int dp[MAXN][MAXN];
int dfs(int i, int j) {
if (dp[i][j] != INF)return dp[i][j];if (i + 2 > j)return 0;if (i + 2 == j)return a[i] * a[i + 1] * a[i + 2];for (int k = i + 1; k < j; k++)dp[i][j] = min(dp[i][j], dfs(i,k) + dfs(k,j)+ a[k]*a[i]*a[j]);return dp[i][j];
}
int main() {
int n;while (cin >> n) {
fill_n(&dp[0][0], MAXN * MAXN, INF);for (int i = 0; i < n; i++)cin >> a[i];cout << dfs(0, n - 1) << endl;}return 0;
}