POJ1651 区间dp-白红宇的个人博客

POJ1651 区间dp

发布日期：2021-06-29 21:39:40 浏览次数：2 分类：技术文章

本文共 1934 字，大约阅读时间需要 6 分钟。

Multiplication Puzzle

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9879		Accepted: 6107

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.

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

610 1 50 50 20 5

Sample Output

3650

题意：给你一个序列，然后让你对他进行移动，顺序任意，每次移动代价是该位置上的数*其左边的第一个数*其右边第一个数，第一个数和最后一个数不能移，让你求出将中间数全部移除之后的最小代价。

思路：一个区间dp，dp[i][j]表示从i到j的最优解，可以考虑从i到k，k+1到j的最小代价，然后可以推出状态转移方程如下；

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=105;

const int INF=0x4fffffff;//无穷大

int a[maxn];

int dp[maxn][maxn];

int main()

{

int n;

while(~scanf("%d",&n))

{

memset(dp,0,sizeof(dp));

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

}

for(int l=2;l<n;l++)//第一个和最后一个不能移，枚举区间长度

{

for(int i=0;i<=n-l+1;i++)//生成左右区间

{

int j=i+l-1;

dp[i][j]=INF;

for(int k=i;k<j;k++)//枚举中点

{

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);

}

printf("%d\n",dp[2][n]);

}

return 0;

}

转载地址：https://dh-butterfly.blog.csdn.net/article/details/70184459 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：HDU4283 区间dp

下一篇：UESTC 1324线段树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章