Multiplication Puzzle

?POJ - 1651?

題意：

在一個序列中，拿走一個數字，那么得分就是這個數字以及它相鄰的兩個數字，這三個數字的乘積。求最小得分。

這道題乍一看感覺是區間DP，但是需要逆向思考的技巧。

記dp[i][k]表示以i開頭的，長度k的區間。

我們考慮一個區間的時候，記錄區間的兩個端點分別為l,r。

這個區間兩側的端點是不能被拿走的，那么我們考慮最后一個被拿走的數字k，它的得分一定是區間端點的兩個數和它的乘積(a[l]*a[k]*a[r])。

然后我們考慮區間[l,k]之間的情況，這個區間被拿的只剩下區間兩個端點了，所以可以直接用子結構dp[l][k-l+1]。

同理區間p[k,r]也被拿的只剩下區間的兩個端點了，直接用子結構dp[k][r-l-k+1]

這樣的話遞推式就非常的清晰了。

dp[i][k] = min(dp[i][k],dp[i][j+1] + dp[i+j][k-j] + a[i]*a[i+j]*a[i+k-1]);//

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAX = 106; int dp[MAX][MAX]; int a[MAX]; int n; int main(){scanf("%d",&n);for(int i = 0;i < n;i++){cin>>a[i];}for(int k = 3;k <= n;k++){for(int i = 0 ;i + k <= n;i++){dp[i][k] = 1e9;for(int j = 1;j < k-1;j++){dp[i][k] = min(dp[i][k],dp[i][j+1] + dp[i+j][k-j] + a[i]*a[i+j]*a[i+k-1]);}}}cout<<dp[0][n]<<endl; }

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的动态规划训练8 [E - Multiplication Puzzle POJ1651]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。