POJ 1651:Multiplication Puzzle 矩阵相乘式DP
2024-10-08 16:55:41
Multiplication Puzzle
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7118 | Accepted: 4385 |
Description
The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on
the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.
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.
the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.
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
The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.
Output
Output must contain a single integer - the minimal score.
Sample Input
6
10 1 50 50 20 5
Sample Output
3650
题意就是给了几个数,依次拿走中间的数,每一次拿走第i个数都会有相应的代价value[i-1]*value[i]*value[i+1],问要求的是给定的序列 拿走所有中间的数 代价最少是多少。
就是矩阵相乘式DP。。。把那个数单提出来想象成要把它第一个拿走就OK了啊,怎么自己的脑筋总是奔到死胡同里面呢,气死我了。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; #define INF 0x3f3f3f3f int dp[105][105];
int value[105];
int num; int main()
{
int i,j,k,len;
scanf("%d",&num); for(i=1;i<=num;i++)
{
scanf("%d",&value[i]);
dp[i][i]=0;
} for(i=1;i<=num;i++)
{
dp[i][i+1] = 0;
dp[i][i+2] = value[i]*value[i+1]*value[i+2];
} for(len=3;len<=num;len++)
{
for(i=1,j=len+i;j<=num;i++)
{
j=len+i;
dp[i][j]=INF;
for(k=i+1;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+value[k]*value[i]*value[j]);//想象成是第一个拿走的
}
}
}
cout<<dp[1][num]<<endl;
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- ubuntu12.04 安装mac主题
- kindeditor多图片上传找不到action原来是private File upload成员变量惹得祸
- ORACLE SQL调优案例一则
- JavaOne_2016演讲视频:
- maven问题-";resolution will not be reattempted until the update interval of MyRepo has elapsed";
- 【干货】Laravel --实战篇 UUID(唯一识别码)
- TYVJ P1083 分糖果 Label:bfs
- 第二章、 Linux 如何学习
- ThinkPHP3.2 加载过程(二)
- 201521123051《java程序设计》 第五周学习总结
- 纯javascript实现可拖住/大小的div
- CSS奇淫技巧
- JEECG3.8 全套实战视频全部开放,免费下载!
- Jmeter下载安装配置及使用(windows)
- leetcode437
- opencv 对RGB图像直接二值化
- Spring WebSocket踩坑指南
- Hibernate里面如何使用DetachedCriteriaCriteria 实现多条件分页查询
- 20155306 白皎 《网络攻防》 EXP7 网络欺诈技术防范
- swoole udp