Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:给的数据过了,怎是wa啊

Posted by lithum at 2009-08-05 14:49:03 on Problem 1651
In Reply To:给的数据过了,怎是wa啊 Posted by:zhanglongpan at 2009-07-27 19:24:43
//此题实际上是一个矩阵连乘问题
//dp[i][j]=min{dp[i][k-1]+dp[k+1][j]+arr[k]*arr[i-1]*arr[j+1] | k}
#include<iostream>
using namespace std;

const int INFINITY=200000000;

int arr[100];
int dp[100][100];
int main()
{
	//freopen("input.txt","r",stdin);
	memset(dp,0,sizeof(dp));
	int i,j,k;
	int length;
	int n;
	int Min,temp;
	cin>>n;
	for(i=0;i<n;i++) cin>>arr[i];
	for(i=1;i<n-1;i++) dp[i][i]=arr[i-1]*arr[i]*arr[i+1];
	for(length=2;length<=n-2;length++){
		for(i=1,j=i+length-1 ; j<=n-2 ; i++,j++){
			Min=INFINITY;
			for(k=i;k<=j;k++){
				temp=dp[i][k-1]+dp[k+1][j]+arr[k]*arr[i-1]*arr[j+1];
				Min=(temp<Min)?temp:Min;
			}
			dp[i][j]=Min;
		}
	}
	cout<<dp[1][n-2]<<endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator