POJ 1651 Multiplication Puzzle，pojmultiplication
Multiplication Puzzle
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 8760
Accepted: 5484
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
10*1*50 + 50*20*5 + 10*50*5 = 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
1*50*20 + 1*20*5 + 10*1*5 = 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
Source
Northeastern Europe 2001, Far-Eastern Subregion
題目大意：有n張寫有數字的卡片，它們排成一行，按一定的順序從中拿走n-2張卡片（第一張和最後一張不能拿走），每次只拿走一張卡片。每拿走一張卡片，同時會獲得一個分數，分數大小為：要拿走的卡片和它左右兩邊的卡片，這三張卡片上的數字乘積。按不同的順序拿走中間n-2張卡片，得到的總分可能不相同，現在要你求出給定一組卡片，按照上述規則拿走卡片的可能的最小總分。
解題思路：一道區間DP的題目。設dp[l][r]表示區間[l,r]的最優解，則狀態轉移如下：
1、當r-l=2時，也即只有三個數時，顯然dp[l][r] = num[l]*num[l+1]*num[r]；
2、當r-l>2時，對區間的最後一個被拿走的數進行枚舉，則dp[l][r] = min(dp[l][r], dp[l][i]+dp[i][r]+num[l]*num[i]*num[r])，其中l<i<r。
附上AC代碼：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int maxn = 105;
6 const int inf = 0x3f3f3f3f;
7 int num[maxn], dp[maxn][maxn];
8 int n;
9
10 int dfs(int l, int r){
11 if (abs(l-r) < 2)
12 return 0;
13 if (r-l == 2)
14 return dp[l][r] = num[l]*num[l+1]*num[r];
15 if (dp[l][r] != inf)
16 return dp[l][r];
17 for (int i=l+1; i<r; ++i)
18 dp[l][r] = min(dp[l][r], dfs(l, i)+dfs(i, r)+num[l]*num[i]*num[r]);
19 return dp[l][r];
20 }
21
22 int main(){
23 while (~scanf("%d", &n)){
24 for (int i=0; i<n; ++i)
25 scanf("%d", num+i);
26 memset(dp, inf, sizeof(dp));
27 dfs(0, n-1);
28 printf("%d\n", dp[0][n-1]);
29 }
30 return 0;
31 }
View Code
