POJ1651 Multiplication Puzzle(DP矩陣鏈)

2019-11-14 13:15:04

字體：大中小

供稿：網(wǎng)友

Multiplication Puzzle Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9500 Accepted: 5906 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

分析矩陣鏈(Matrix Chain)，用迭代實現(xiàn)動態(tài)規(guī)劃. 我把分析放在了代碼注釋中

感受剛開始一直看別人代碼，看不懂后來拿紙一步一步算總算弄明白了,Orz看十遍不如親手算一遍.

#include<cstdio>#include<iostream>#include<algorithm>#include<cmath> #include<vector>using namespace std;#define inf 0x3fffffff#define maxn 105int p[maxn];// 表示矩陣的行數(shù), 注意我是從0開始的 int m[maxn][maxn];//m[i][j]表示從第i個矩陣鏈到第j個矩陣鏈的最少相乘次數(shù) int s[maxn][maxn];//s[i][j]表示從第i個矩陣鏈到第j個矩陣鏈的分界點(diǎn)（也就是解的追蹤),在本題中可以不寫 void matrix_chain(int* p,int n,int m[maxn][maxn],int s[maxn][maxn]){ for(int i=0;i<=n;i++) m[i][i]=0; for(int len=2;len<n;len++)//len:鏈長 for(int i=1;i<=n-len+1;i++)// i:左邊界 (i=1,表示第i個矩陣鏈) { int j=i+len-1;//通過左邊界i和鏈長r可確定右邊界j (j:第j個矩陣鏈) m[i][j]=inf;// init for(int k=i;k<=j-1;k++){ int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if( t < m[i][j]){ m[i][j]=t; //更新解 s[i][j]=k; } } } }//print_parens的功能是打印括弧，本題可以不要. //paren : 括弧//感覺和線段樹有點(diǎn)相似,對著樣例把這個樹畫出來就懂了，圖在代碼的最下面*/ void print_parens(int s[maxn][maxn],int i ,int j) { if(i==j) printf("A%d",i); else { printf("("); print_parens(s,i,s[i][j]); print_parens(s,s[i][j]+1,j);//遞歸調(diào)用 printf(")"); } } int main(){ //freopen("in.txt","r",stdin); int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&p[i]); } matrix_chain(p,n,m,s); printf("%d/n",m[1][n-1]); /* printf("%d/n",s[1][n-1]); printf("%d/n",s[2][n-1]); printf("%d/n",s[2][4]); printf("/nprint_parens:/n"); print_parens(s,1,n-1); */ return 0; }

關(guān)于print_parens的理解 下圖是依據(jù)樣例可以畫出的樹,然后按照先序遍歷訪問所有節(jié)點(diǎn). 這里寫圖片描述對于綠色節(jié)點(diǎn): 第一次訪問打印左括弧(即入棧時打印“(”) ,第二次訪問打印右括弧(即出棧時打印”)”) 對于紅色節(jié)點(diǎn): 直接輸出Ai