ccbeginner

UVa Q348 (help me...)

Jan 15th, 2020
105
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q348
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int dp[11][11];
  6. int trans[11][11];
  7. int arr[11];
  8. string ans;
  9.  
  10. void getans(int l, int r){
  11.     if(l == r){
  12.         ans += "A";
  13.         if(l == 9)ans += "10";
  14.         else ans += (char)(l+'1');
  15.         return;
  16.     }
  17.     ans += "(";
  18.     getans(l, trans[l][r]);
  19.     ans += " x ";
  20.     getans(trans[l][r]+1, r);
  21.     ans += ")";
  22. }
  23.  
  24. int32_t main(){
  25.     int n;
  26.     int cnt = 0;
  27.     while(cin >> n){
  28.         if(n == 0)break;
  29.         for(int i = 0; i <= n; ++i)
  30.             for(int j = 0; j <= n; ++j)
  31.                 if(i != j)dp[i][j] = INT_MAX;
  32.         for(int i = 0; i < n; ++i)cin >> arr[i] >> arr[i+1];
  33.         for(int l = 1; l < n; ++l){
  34.             for(int i = 0; i+l < n; ++i){
  35.                 int j = i+l;
  36.                 for(int k = i; k < j; ++k){
  37.                     if(dp[i][j] > dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1]){
  38.                         dp[i][j] = dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1];
  39.                         trans[i][j] = k;
  40.                     }
  41.                 }
  42.                 //cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
  43.             }
  44.         }
  45.         getans(0, n-1);
  46.         cout << "Case " << ++cnt << ": " << ans << '\n';
  47.         ans = "";
  48.     }
  49.     return 0;
  50. }
RAW Paste Data