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 Calciver at 2012-03-13 19:44:08 on Problem 1651
In Reply To:Re:给的数据过了,怎是wa啊 Posted by:lithum at 2009-08-05 14:49:03
> //此题实际上是一个矩阵连乘问题
> //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