首页 > 代码库 > poj - 1651 - Multiplication Puzzle(dp)
poj - 1651 - Multiplication Puzzle(dp)
题意:n个数(3 <= N <= 100)的序列,每次取一个数(不可以取最左最右)a[k],这时得到一个权值为a[k]左边的数 * a[k] * a[k]右边的数,问最小权值和。
题目链接:http://poj.org/problem?id=1651
——>>状态:dp[i][j]表示第i个数到第j个数组成的序列的最小权值和。
状态转移方程:dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);(枚举最后一个拿掉的数来更新)
时间复杂度:O(n ^ 3)
#include <cstdio> #include <algorithm> #include <cstring> using std::min; const int MAXN = 100 + 1; int a[MAXN]; int dp[MAXN][MAXN]; void Read(int n) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } } void Dp(int n) { memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i < n; ++i) { dp[i][i + 1] = 0; } for (int nLen = 3; nLen <= n; ++nLen) { for (int i = 1; i <= n; ++i) { int j = i + nLen - 1; if (j > n) break; for (int k = i + 1; k < j; ++k) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); } } } } void Output(int n) { printf("%d\n", dp[1][n]); } int main() { int n; while (scanf("%d", &n) == 1) { Read(n); Dp(n); Output(n); } return 0; }
poj - 1651 - Multiplication Puzzle(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。