POJ1651 Multiplication Puzzle —— DP 最优矩阵链乘 区间DP
题目链接:https://vjudge.net/problem/POJ-1651
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 11239 | Accepted: 6980 |
Description
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
Output
Sample Input
6
10 1 50 50 20 5
Sample Output
3650
Source
题意:
有N张写有数字的卡片排成一行,按一定次序从中拿走N-2张(第1张和最后一张不能拿),每次只拿一张,取走一张卡片的同时,会得到一个分数,分值的计算方法是:要拿的卡片,和它左右两边的卡片,这三张卡片上数字的乘积。按不同的顺序取走N-2张卡片,得到的总分可能不相同,求出给定一组卡片按上述规则拿取的最小得分。
题解:
最优矩阵链乘问题。刘汝佳紫书P277。
1.在取牌的过程中,必定存在一张最后取的牌,可知这张牌左右两边的牌都已经取完了(除了两端点)。于是“最后取的牌”,就把区间分成了两段。由于这两段区间的取牌(即得分情况)互不影响,故可以分开求值。那又怎样才能知道最后取哪张牌才能使得取值最优呢?枚举区间内每一张牌作为最后取的牌,取最优值。
2.对于被分开的左右两段区间,又可各自根据步骤1得到最优值。
3.紫书中区间的写法是左闭右开,但个人觉得不好理解,于是就写成自己所熟悉的闭区间。
记忆化搜索:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ms(a, b) memset((a), (b), sizeof(a))
#define eps 0.0000001
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+;
const int maxn = +; LL p[maxn], dp[maxn][maxn]; LL dfs(int l, int r) //区间[l, r]中每个元素都可以取走
{
if(l>r) return ;
if(dp[l][r]!=LNF) return dp[l][r]; for(int k = l; k<=r; k++)
dp[l][r] = min(dp[l][r], dfs(l,k-) + dfs(k+,r) + p[l-]*p[k]*p[r+]); return dp[l][r];
} int main()
{
int n;
scanf("%d",&n);
for(int i = ; i<=n; i++)
scanf("%lld",&p[i]); for(int i = ; i<n; i++)
for(int j = ; j<=n; j++)
dp[i][j] = LNF; cout<<dfs(, n-)<<endl;
return ;
}
递推:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ms(a, b) memset((a), (b), sizeof(a))
#define eps 0.0000001
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+;
const int maxn = +; LL p[maxn], dp[maxn][maxn]; int main()
{
int n;
scanf("%d",&n);
for(int i = ; i<=n; i++)
scanf("%lld",&p[i]); memset(dp, , sizeof(dp));
for(int l = ; l<=n-; l++)
for(int r = l; r<=n-; r++)
dp[l][r] = LNF; for(int len = ; len<=n-; len++)
{
for(int l = ; l<=n--len+; l++) //能取的区间为[2, n-1]
{
int r = l + len - ;
for(int k = l; k<=r; k++)
dp[l][r] = min(dp[l][r], dp[l][k-] + dp[k+][r] + p[l-]*p[k]*p[r+]);
}
} cout<< dp[][n-] <<endl; }
最新文章
- 【译】RabbitMQ:工作队列(Work Queue)
- XAF学习笔记1
- bios中只有windows boot manager下用U盘启动
- iOS 关于AFNetworking ssl 待完成
- [原]运行编译好的Android模拟器
- appt查看apk信息
- 使用dreamever去掉文件头部BOM(bom)信息 From 百度经验
- JAVA zip解压 MALFORMED 错误
- C# static成员的构造顺序
- chrome浏览器调试
- 宏汇编软件MASM51的使用
- SSH服务端配置、优化加速、安全防护
- Storm业务功能
- 关于t,f test
- window下安装 node ,并搭建 vue 项目
- C. Multiplicity 简单数论+dp(dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 前面序列要满足才能构成后面序列)+sort
- eclemma怎么安装 eclemma的安装与简单使用图文教程(附下载)
- python 模块之-ffmpeg 中文参数对照表
- 2017-2018-2 20165231实验二《Java面向对象程序设计》实验报告
- [编程小技巧]Notepad++中如何实现文本对比功能?