首页 > 代码库 > poj1651 Multiplication Puzzle(简单区间dp)
poj1651 Multiplication Puzzle(简单区间dp)
题目链接:http://poj.org/problem?id=1651
题意:一系列的数字,除了头尾不能动,每次取出一个数字,这个数字与左右相邻数字的乘积为其价值,
最后将所有价值加起来,要求最小值。
这题容易会想到贪心就是先把最大的数先取出这样就能满足剩下的总价值尽可能的小,如果出现多个一样
的数时优先取走价值小的,但是如果有出现多个价值一样的话就不好处理了。
于是可以考虑一下用区间解决,区间转移大致是这样的
dp[j][j + i] = min(dp[j][j + i] , dp[j][k] + dp[k][j + i] + a[k] * a[j] * a[j + i]);
(i表示区间长度,j表示区间起点,k表示区间中枚举的点)
#include <iostream>#include <cstring>#include <algorithm>using namespace std;int a[110] , dp[110][110];int main() { int n; cin >> n; for(int i = 1 ; i <= n ; i++) cin >> a[i]; memset(dp , 0X3f3f3f3f , sizeof(dp)); for(int i = 1 ; i < n ; i++) { dp[i][i + 1] = 0; } for(int i = 2 ; i < n ; i++) { for(int j = 1 ; j <= n && j + i <= n ; j++) { for(int k = j + 1 ; k < i + j ; k++) { dp[j][j + i] = min(dp[j][j + i] , dp[j][k] + dp[k][j + i] + a[k] * a[j] * a[j + i]); } } } cout << dp[1][n] << endl; return 0;}
poj1651 Multiplication Puzzle(简单区间dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。