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大学生程序设计竞赛训练》暑期课面向全球招生!

DP过~~(矩阵乘法)

Posted by 20051106 at 2017-07-02 20:57:34 on Problem 1651
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <deque>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <map>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>
#include <cwchar>
#include <cwctype>
#define mp make_pair
#define fs first
#define se second
#define memset(a,t) memset(a,t,sizeof(a))
#define all(v) v.begin(),v.end()
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define MN 0LL
#define MX 20000000000000005
using namespace std;
long long dp[105][105];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	long long n,i,j,k,s;
	for(i=1;i<105;i++) for(j=1;j<105;j++) dp[i][j]=MX;
	long long m[105];
	cin>>n;
	for(i=1;i<=n;i++) cin>>m[i];
	for(i=1;i<=n;i++) dp[i][i]=0;
	for(s=1;s<=n-1;s++){
		for(i=1;i<=n-s;i++){
			j=i+s;
			for(k=i;k<j;k++){
				dp[i][j]=min(dp[i][j],dp[k+1][j]+dp[i][k]+m[i-1]*m[k]*m[j]);
			}
		}
	}
//	for(i=1;i<=n;i++){
//		for(j=1;j<=n;j++) cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
	cout<<dp[2][n]<<endl;
	return 0;
	#ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
}

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