小说网站设计模板,网站外包怎么做,设计软件下载,wordpress google推广Multiplication Puzzle POJ - 1651 题意#xff1a;
在一个序列中#xff0c;拿走一个数字#xff0c;那么得分就是这个数字以及它相邻的两个数字#xff0c;这三个数字的乘积。求最小得分。
这道题乍一看感觉是区间DP#xff0c;但是需要逆向思考的技巧。
记dp[i][k]… Multiplication Puzzle POJ - 1651 题意
在一个序列中拿走一个数字那么得分就是这个数字以及它相邻的两个数字这三个数字的乘积。求最小得分。
这道题乍一看感觉是区间DP但是需要逆向思考的技巧。
记dp[i][k]表示以i开头的长度k的区间。
我们考虑一个区间的时候记录区间的两个端点分别为l,r。
这个区间两侧的端点是不能被拿走的那么我们考虑最后一个被拿走的数字k它的得分一定是区间端点的两个数和它的乘积(a[l]*a[k]*a[r])。
然后我们考虑区间[l,k]之间的情况这个区间被拿的只剩下区间两个端点了所以可以直接用子结构dp[l][k-l1]。
同理区间p[k,r]也被拿的只剩下区间的两个端点了直接用子结构dp[k][r-l-k1]
这样的话递推式就非常的清晰了。 dp[i][k] min(dp[i][k],dp[i][j1] dp[ij][k-j] a[i]*a[ij]*a[ik-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){cina[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][j1] dp[ij][k-j] a[i]*a[ij]*a[ik-1]);}}}coutdp[0][n]endl;
}
