fork(19) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n;
  8. vector <int> v;
  9. void f(long long **a, long long i, long long j ){
  10. 	if(a[j][i]>0){
  11. 		v.push_back(a[j][i]);
  12. 		if((a[j][i]<=n)&&(i<=n)&&(j<=n)){
  13. 			f(a,i,a[j][i]);
  14. 			f(a,a[j][i],j);
  15. 		}
  16. 	}
  17. }
  18. string answer(long long x, long long si, long long sj, long long el){
  19. 	 long long z1=el,z2=el;
  20. 	 if(sj!=si){
  21. 	 	if(si!=x){
  22.             while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;
  23. 	 	}
  24. 	 	if(sj!=(x+1)){
  25. 	 		while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++; 
  26. 	 	}
  27. 	 }
  28. 	return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";
  29. }
  30. int main() {
  31. 	long long i,j,useless,number=1,**dp;
  32. 	cin>>n;
  33. 	while(n){
  34. 		n++;
  35. 		dp = new long long* [n];
  36. 		for(i=0;i<n;i++)dp[i]=new long long [n];
  37. 		for(i=0;i<n;i++){
  38. 			for(j=0;j<n;j++){
  39. 				dp[i][j]=0;
  40. 			}
  41. 		}
  42. 		cin>>dp[0][0];
  43. 		for(i=1;i<n;i++){
  44. 			cin>>dp[i][i];
  45. 			if(i<(n-1))cin>>useless;
  46. 		}
  47. 		i=2;
  48. 		for(i=2;i<n;i++){		
  49. 			for(j=0;j<=(i-2);j++){
  50. 				dp[i][j]=2e10;
  51. 			}
  52. 		}
  53. 		long long t;
  54. 		for(i=2;i<n;i++){
  55. 			for(j=0;j<(n-i);j++){
  56. 				long long k=j+i;
  57. 				for(t=1;(j+t)<(n-1);t++){
  58. 					if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){
  59. 						dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];
  60. 						dp[j][k]=j+t;
  61. 					}
  62. 				}
  63. 			}
  64. 		}
  65. 		f(dp,n-1,0);
  66. 		reverse(v.begin(),v.end());
  67. 		cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';
  68. 		number++;
  69. 		delete [] dp;
  70. 		v.clear();
  71. 		cin>>n;
  72. 	}
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
2
11 12
12 33
7
1 5
5 28
28 19
19 2
2 10
10 1
1 12
4
10 29
29 133
133 8
8 15
0
stdout
copy 
Case 1: (A1 x A2)
Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7)
Case 3: ((A1 x (A2 x A3)) x A4)
https://ideone.com/FGea1P
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!